c/c++语言开发共享C++实现LeetCode(648.替换单词)

[leetcode] 648.replace words 替换单词

in english, we have a concept called root, which can be followed by some other words to form another longer word – let’s call this word successor. for example, the root an, followed by other, which can form another word another.

now, given a dictionary consisting of many roots and a sentence. you need to replace all the successor in the sentence with the root forming it. if a successor has many roots can form it, replace it with the root with the shortest length.

you need to output the sentence after the replacement.

example 1:

input: dict = [“cat”, “bat”, “rat”]
sentence = “the cattle was rattled by the battery”
output: “the cat was rat by the bat”

note:

1. the input will only have lower-case letters.
2. 1 <= dict words number <= 1000
3. 1 <= sentence words number <= 1000
4. 1 <= root length <= 100
5. 1 <= sentence words length <= 1000

这道题给了我们一个前缀字典，又给了一个句子，让我们将句子中较长的单词换成其前缀(如果在前缀字典中存在的话)。我们对于句子中的一个长单词如何找前缀呢，是不是可以根据第一个字母来快速定位呢，比如cattle这个单词的首字母是c，那么我们在前缀字典中找所有开头是c的前缀，为了方便查找，我们将首字母相同的前缀都放到同一个数组中，总共需要26个数组，所以我们可以定义一个二维数组来装这些前缀。还有，我们希望短前缀在长前缀的前面，因为题目中要求用最短的前缀来替换单词，所以我们可以先按单词的长度来给所有的前缀排序，然后再依次加入对应的数组中，这样就可以保证短的前缀在前面。

下面我们就要来遍历句子中的每一个单词了，由于c++中没有split函数，所以我们就采用字符串流来提取每一个单词，对于遍历到的单词，我们根据其首字母查找对应数组中所有以该首字母开始的前缀，然后直接用substr函数来提取单词中和前缀长度相同的子字符串来跟前缀比较，如果二者相等，说明可以用前缀来替换单词，然后break掉for循环。别忘了单词之前还要加上空格，参见代码如下：

解法一：

  class solution {  public:      string replacewords(vector<string>& dict, string sentence) {          string res = "", t = "";          vector<vector<string>> v(26);          istringstream is(sentence);          sort(dict.begin(), dict.end(), [](string &a, string &b) {return a.size() < b.size();});          for (string word : dict) {              v[word[0] - 'a'].push_back(word);          }          while (is >> t) {              for (string word : v[t[0] - 'a']) {                  if (t.substr(0, word.size()) == word) {                      t = word;                      break;                  }              }              res += t + " ";          }          res.pop_back();          return res;      }  };

你以为想出了上面的解法，这道题就算做完了？? naive! ! ! 这道题最好的解法其实是用前缀树(trie / prefix tree)来做，关于前缀树使用之前有一道很好的入门题implement trie (prefix tree)。了解了前缀树的原理机制，那么我们就可以发现这道题其实很适合前缀树的特点。我们要做的就是把所有的前缀都放到前缀树里面，而且在前缀的最后一个结点的地方将标示isword设为true，表示从根节点到当前结点是一个前缀，然后我们在遍历单词中的每一个字母，我们都在前缀树查找，如果当前字母对应的结点的表示isword是true，我们就返回这个前缀，如果当前字母对应的结点在前缀树中不存在，我们就返回原单词，这样就能完美的解决问题了。所以啊，以后遇到了有关前缀或者类似的问题，一定不要忘了前缀树这个神器哟～

解法二：

  class solution {  public:      class trienode {      public:          bool isword;          trienode *child[26];          trienode(): isword(false) {              for (auto &a : child) a = null;          }      };            string replacewords(vector<string>& dict, string sentence) {          string res = "", t = "";          istringstream is(sentence);          trienode *root = new trienode();          for (string word : dict) {              insert(root, word);          }          while (is >> t) {              if (!res.empty()) res += " ";              res += findprefix(root, t);          }          return res;      }            void insert(trienode* node, string word) {          for (char c : word) {              if (!node->child[c - 'a']) node->child[c - 'a'] = new trienode();              node = node->child[c - 'a'];          }          node->isword = true;      }            string findprefix(trienode* node, string word) {          string cur = "";          for (char c : word) {              if (!node->child[c - 'a']) break;              cur.push_back(c);              node = node->child[c - 'a'];              if (node->isword) return cur;          }          return word;      }  };

类似题目：

implement trie (prefix tree)

参考资料：

到此这篇关于c++实现leetcode(648.替换单词)的文章就介绍到这了,更多相关c++实现替换单词内容请搜索<计算机技术网(www.ctvol.com)!!>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网(www.ctvol.com)!!>！

需要了解更多c/c++开发分享C++实现LeetCode(648.替换单词)，都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!