Java实现 LeetCode 648 单词替换（字典树）

￡神魔★判官ぃ 2023-07-21 05:46 31阅读 0赞

## 648. 单词替换 ##

在英语中，我们有一个叫做 词根(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 { 
        public String replaceWords(List<String> dict, String sentence) { 
            Trie trie = new Trie();
            for(String word : dict){ 
                trie.insert(word);
            }
            String[] words = sentence.split(" ");
            StringBuilder sb = new StringBuilder();
            for(String word : words){ 
                sb.append(trie.change(word)).append(" ");
            }
            return sb.toString().substring(0,sb.toString().length()-1);
        }
    }
    
    class Trie{ 
        TrieNode root;
        public Trie(){ 
            root = new TrieNode();
        }
        public void insert(String word){ 
            TrieNode node = root;
            for(char c : word.toCharArray()){ 
                if(node.link[c - 'a'] == null){ 
                    node.link[c - 'a'] = new TrieNode();
                }
                node =  node.link[c - 'a'];
            }
            node.isEnd = true;
        }
    
           public String change(String word){ 
            StringBuilder sb = new StringBuilder();
            TrieNode node = root;
            boolean found = false;
            for(char c :word.toCharArray()){ 
                if(node.link[c - 'a'] == null){ 
                    break;
                }
                else{ 
                    sb.append(c);
                    node = node.link[c - 'a'];
                    if(node.isEnd){ 
                        return sb.toString();
                    }
                }
            }
            return word;
        }
    }
    
    class TrieNode{ 
        TrieNode[] link;
        boolean isEnd;
    
        public TrieNode() { 
            link = new TrieNode[26];
            isEnd = false;
        }
    }