原题

在英语中，我们有一个叫做 词根(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 {
    class TrieNode{
        TrieNode[] children = new TrieNode[26];
        String word;
    }

    public String replaceWords(List<String> dict, String sentence) {
        StringBuilder sb = new StringBuilder();
        TrieNode root = new TrieNode();
        for(String word:dict) insertToTrie(root,word);
        String[] words = sentence.split(" ");
        for(int i = 0;i<words.length;i++){
            String prefix = hasPrefix(root,words[i]);
            if(!prefix.equals("")) words[i] = prefix;
        }
        for(int i = 0;i<words.length;i++){
            sb.append(words[i]);
            if(i!=words.length-1) sb.append(" ");
        }
        return sb.toString();
    }

    /*将前缀插入字典树*/
    public void insertToTrie(TrieNode root,String word){
        TrieNode cur = root;
        for(char i:word.toCharArray()){
            if(cur.children[i-'a']==null){
                cur.children[i-'a'] = new TrieNode();
            }
            cur = cur.children[i-'a'];
        }
        cur.word = word;
    }

    /*从字典树中获取前缀*/
    public String hasPrefix(TrieNode root,String word){
        TrieNode cur = root;
        for(char i:word.toCharArray()){
            if(cur.children[i-'a']==null){
                return "";
            }
            cur = cur.children[i-'a'];
            if(cur.word!=null){;
                return cur.word;
            }
        }
        return "";
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode648-%e5%8d%95%e8%af%8d%e6%9b%bf%e6%8d%a2/