Java实现 LeetCode 648 单词替换（字典树）-蒲公英云

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

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;
    }
}