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"
按照题意，基本上能够马上知道这题需要用trie
1 class Solution { 2 public String replaceWords(List<String> dict, String sentence) { 3 String[] tokens = sentence.split(" "); 4 TrieNode trie = buildTrie(dict); 5 return replaceWords(tokens, trie); 6 } 7 8 private String replaceWords(String[] tokens, TrieNode root) { 9 StringBuilder stringBuilder = new StringBuilder(); 10 for (String token : tokens) { 11 stringBuilder.append(getShortestReplacement(token, root)); 12 stringBuilder.append(" "); 13 } 14 return stringBuilder.substring(0, stringBuilder.length()-1); 15 } 16 17 private String getShortestReplacement(String token, final TrieNode root) { 18 TrieNode temp = root; 19 StringBuilder stringBuilder = new StringBuilder(); 20 for (char c : token.toCharArray()) { 21 stringBuilder.append(c); 22 if (temp.map.containsKey(c)) { 23 if (temp.map.get(c).isWord) { 24 return stringBuilder.toString(); 25 } 26 temp = temp.map.get(c); 27 } else { 28 return token; 29 } 30 } 31 return token; 32 } 33 34 private TrieNode buildTrie(List<String> dict) { 35 TrieNode root = new TrieNode(‘ ‘); 36 for (String word : dict) { 37 TrieNode current = root; 38 for (char ch : word.toCharArray()) { 39 TrieNode node = current.getChildNode(ch); 40 if (node == null) { 41 current.map.put(ch, new TrieNode(ch)); 42 node = current.getChildNode(ch); 43 } 44 current = node; 45 } 46 current.isWord = true; 47 } 48 return root; 49 } 50 } 51 52 class TrieNode { 53 char ch; 54 boolean isWord; 55 Map<Character, TrieNode> map; 56 57 public TrieNode(char ch) { 58 this.ch = ch; 59 map = new HashMap<>(); 60 } 61 62 public TrieNode getChildNode(char ch) { 63 return map.get(ch); 64 } 65 }
原文：https://www.cnblogs.com/beiyeqingteng/p/11149055.html