题目地址：https://leetcode.com/problems/replace-words/description/
题目描述
InEnglish, 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.
Youneed 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、 Theinputwillonlyhavelower-caseletters.；
2、 1<=dictwordsnumber<=1000；
3、 1<=sentencewordsnumber<=1000；
4、 1<=rootlength<=100；
5、 1<=sentencewordslength<=1000；
题目大意
把句子中的每个单词用给的字典进行替换，替换时优先替换成最短的词。替换就是找出最短的头部匹配；如果字典中不存在，就保留原来的词。
解题方法
set
看了下给出的Note，发现并没有特别长，普通的方法应该就能搞定，不会超时。
下面的方法叫做Prefix Hash，对于python而言就是用了set的意思。
class Solution(object):
def replaceWords(self, dict, sentence):
"""
:type dict: List[str]
:type sentence: str
:rtype: str
"""
rootset = set(dict)
def replace(word):
for i in xrange(len(word)):
if word[:i] in rootset:
return word[:i]
return word
return ' '.join(map(replace, sentence.split()))
1 2 3 4 5 6 7 8 9 10 11 12 13 14
字典
用数组保存dict中，每个小写字符开头的单词。然后对给出的句子进行遍历每个单词，判断这个单词能不能用更短的前缀替换。题目中要求用尽可能短的单词进行替换，所以需要排序，让短的单词在前面。
class Solution {
public:
string replaceWords(vector<string>& dict, string sentence) {
vector<vector<string>> m(26);
sort(dict.begin(), dict.end(), [](string a, string b) {
return a.size() < b.size();});
for (string s : dict)
m[s[0] - 'a'].push_back(s);
istringstream is(sentence);
string cur;
string res;
while (is >> cur) {
for (string word : m[cur[0] - 'a']) {
if (word == cur.substr(0, word.size())) {
cur = word;
break;
}
}
res += cur + ' ';
}
res.pop_back();
return res;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
前缀树
前缀树，又称字典树Trie。具体实现可以看208. Implement Trie (Prefix Tree)open in new window。
这个题里面，使用了Trie。做法比较简单，把所有的字典前缀放入Trie里面，然后再查句子每个单词是否在里面即可。
需要注意的是，我们的根节点没有存储字符，遍历Trie的时候，p的child数组是我们对应的当前字符。如果当前节点是单词，就直接返回了。如果当前节点不是单词，然后它的child又是空，说明不符合要查找的字符串。就返回掉原始字符串即可。
class TrieNode {
public:
vector<TrieNode*> child;
bool isWord;
TrieNode() : isWord(false), child(26, nullptr){};
~TrieNode() {
for (auto& a : child)
delete a;
}
};
class Solution {
public:
string replaceWords(vector<string>& dict, string sentence) {
root = new TrieNode();
for (string& d : dict) {
insert(d);
}
istringstream is(sentence);
string res;
string cur;
while (is >> cur) {
res += getPrefix(cur) + ' ';
}
res.pop_back();
return res;
}
string getPrefix(string word) {
TrieNode* p = root;
string path;
for (char& c : word) {
int i = c - 'a';
if (p->isWord)
return path;
if (!p->child[i])
return word;
path += c;
p = p->child[i];
}
return word;
}
void insert(string word) {
TrieNode* p = root;
for (char& c : word) {
int i = c - 'a';
if (!p->child[i])
p->child[i] = new TrieNode();
p = p->child[i];
}
p->isWord = true;
}
private:
TrieNode* root;
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发