在英语中,有一个叫做 词根(root) 的概念,它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如,词根an,跟随着单词 other(其他),可以形成新的单词 another(另一个)。现在,给定一个由许多词根组成的词典和一个句子,需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根,则用最短的词根替换它。需要输出替换之后的句子。
示例 1:
输入:dictionary = [“cat”,“bat”,“rat”], sentence = “the cattle was rattled by the battery”
输出:“the cat was rat by the bat”
找到替换单词的前缀,返回直接赋值,如果没有找到则返回一个空字符串。
class Solution {
class TrieNode{
TrieNode []children;
boolean isWord;
public TrieNode(){
children = new TrieNode[26];
}
}
public String replaceWords(List<String> dictionary, String sentence) {
TrieNode root = builder(dictionary);
String []words = sentence.split(" ");
for(int i = 0; i < words.length ; i++){
String prefix = searchPrefix(root,words[i]);
if(!prefix.isEmpty()){
words[i] = prefix;
}
}
return String.join(" ",words);
}
public TrieNode builder(List<String> dictionary){
TrieNode root = new TrieNode();
for(String s : dictionary){
TrieNode node = root;
for(char ch : s.toCharArray()){
if(node.children[ch - 'a'] == null){
node.children[ch - 'a'] = new TrieNode();
}
node = node.children[ch - 'a'];
}
node.isWord = true;
}
return root;
}
public String searchPrefix(TrieNode root,String word){
TrieNode node = root;
StringBuilder sb = new StringBuilder();
for(char ch : word.toCharArray()){
if(node.isWord || node.children[ch - 'a'] == null){
break;
}
sb.append(ch);
node = node.children[ch - 'a'];
}
return node.isWord ? sb.toString() : "";
}
}