【剑指OfferII】063.替换单词

题目&＃xff1a;
在英语中&＃xff0c;有一个叫做 词根(root) 的概念&＃xff0c;它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如&＃xff0c;词根an&＃xff0c;跟随着单词 other(其他)&＃xff0c;可以形成新的单词 another(另一个)。

现在&＃xff0c;给定一个由许多词根组成的词典和一个句子&＃xff0c;需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根&＃xff0c;则用最短的词根替换它。

需要输出替换之后的句子。

示例 1&＃xff1a;

输入&＃xff1a;dictionary &＃61; [“cat”,“bat”,“rat”], sentence &＃61; “the cattle was rattled by the battery”
输出&＃xff1a;“the cat was rat by the bat”

示例 2&＃xff1a;

输入&＃xff1a;dictionary &＃61; [“a”,“b”,“c”], sentence &＃61; “aadsfasf absbs bbab cadsfafs”
输出&＃xff1a;“a a b c”

示例 3&＃xff1a;

输入&＃xff1a;dictionary &＃61; [“a”, “aa”, “aaa”, “aaaa”], sentence &＃61; “a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa”
输出&＃xff1a;“a a a a a a a a bbb baba a”

示例 4&＃xff1a;

输入&＃xff1a;dictionary &＃61; [“catt”,“cat”,“bat”,“rat”], sentence &＃61; “the cattle was rattled by the battery”
输出&＃xff1a;“the cat was rat by the bat”

示例 5&＃xff1a;

输入&＃xff1a;dictionary &＃61; [“ac”,“ab”], sentence &＃61; “it is abnormal that this solution is accepted”
输出&＃xff1a;“it is ab that this solution is ac”

提示&＃xff1a;

1 <&＃61; dictionary.length <&＃61; 1000
1 <&＃61; dictionary[i].length <&＃61; 100
dictionary[i] 仅由小写字母组成。
1 <&＃61; sentence.length <&＃61; 10^6
sentence 仅由小写字母和空格组成。
sentence 中单词的总量在范围 [1, 1000] 内。
sentence 中每个单词的长度在范围 [1, 1000] 内。
sentence 中单词之间由一个空格隔开。
sentence 没有前导或尾随空格。

注意&＃xff1a;本题与主站 648 题相同&＃xff1a; https://leetcode-cn.com/problems/replace-words/

答案&＃xff1a;

class Solution {//设计前缀树的数据结构public class TrieNode{boolean isEnd;TrieNode[] next;TrieNode(){next &＃61; new TrieNode[26];}}public String replaceWords(List<String> dictionary, String sentence) {//使用前缀树//将字典插入前缀树TrieNode root &＃61; new TrieNode();for(int i &＃61; 0; i < dictionary.size(); i&＃43;&＃43;){TrieNode node &＃61; root;for(char c : dictionary.get(i).toCharArray()){if(node.next[c - &＃39;a&＃39;] &＃61;&＃61; null){node.next[c - &＃39;a&＃39;] &＃61; new TrieNode();}node &＃61; node.next[c - &＃39;a&＃39;];}node.isEnd &＃61; true;}//判断sentenceString[] strs &＃61; sentence.split(" ");StringBuffer sb &＃61; new StringBuffer();for(String str : strs){TrieNode node &＃61; root;StringBuffer temp &＃61; new StringBuffer();for(char c : str.toCharArray()){if(node.next[c - &＃39;a&＃39;] &＃61;&＃61; null){sb.append(str);temp &＃61; new StringBuffer();break;}else{temp.append(c);//System.out.println(c);if(node.next[c - &＃39;a&＃39;].isEnd &＃61;&＃61; true) break;node &＃61; node.next[c - &＃39;a&＃39;];}}sb.append(temp);sb.append(" ");}sb.deleteCharAt(sb.length() - 1);return sb.toString();}
}