原题
在英语中，我们有一个叫做 词根(root)的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。
现在，给定一个由许多词根组成的词典和一个句子。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
你需要输出替换之后的句子。
示例1:
输入: dict(词典) = ["cat", "bat", "rat"] sentence(句子) = "the cattle was rattled by the battery"
输出: "the cat was rat by the bat"
注:
- 输入只包含小写字母。
- 1 <= 字典单词数 <=1000
- 1 <= 句中词语数 <= 1000
- 1 <= 词根长度 <= 100
- 1 <= 句中词语长度 <= 1000
解法
思想
这里的词根其实就是字符串的前缀，一开始我以为出现在哪都可以。前缀可以使用字典树搜索。
代码
class Solution {
class TrieNode{
TrieNode[] children = new TrieNode[26];
String word;
}
public String replaceWords(List<String> dict, String sentence) {
StringBuilder sb = new StringBuilder();
TrieNode root = new TrieNode();
for(String word:dict) insertToTrie(root,word);
String[] words = sentence.split(" ");
for(int i = 0;i<words.length;i++){
String prefix = hasPrefix(root,words[i]);
if(!prefix.equals("")) words[i] = prefix;
}
for(int i = 0;i<words.length;i++){
sb.append(words[i]);
if(i!=words.length-1) sb.append(" ");
}
return sb.toString();
}
/*将前缀插入字典树*/
public void insertToTrie(TrieNode root,String word){
TrieNode cur = root;
for(char i:word.toCharArray()){
if(cur.children[i-'a']==null){
cur.children[i-'a'] = new TrieNode();
}
cur = cur.children[i-'a'];
}
cur.word = word;
}
/*从字典树中获取前缀*/
public String hasPrefix(TrieNode root,String word){
TrieNode cur = root;
for(char i:word.toCharArray()){
if(cur.children[i-'a']==null){
return "";
}
cur = cur.children[i-'a'];
if(cur.word!=null){;
return cur.word;
}
}
return "";
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode648-%e5%8d%95%e8%af%8d%e6%9b%bf%e6%8d%a2/
