原文链接: https://leetcode-cn.com/problems/UhWRSj

中文题目

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

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

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

 

示例 1：

输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"

示例 2：

输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
输出："a a b c"

示例 3：

输入：dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
输出："a a a a a a a a bbb baba a"

示例 4：

输入：dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"

示例 5：

输入：dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted"
输出："it is ab that this solution is ac"

 

提示：

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

 

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

通过代码

高赞题解

先构造前缀树的数据结构然后完成需要的功能即可满足题目需求

class Solution {
    //前缀树数据结构是一个字符多叉树，用一个数组来保存其子节点， isValid用来标记截止到该节点是否为一个完整的单词
    class TrieNode{
        TrieNode[] kids;
        boolean isValid;
        public TrieNode(){
            kids = new TrieNode[26];
        }
    }

    TrieNode root = new TrieNode();
    public String replaceWords(List<String> dictionary, String sentence) {
        String[] words = new String[dictionary.size()];
        for(int i = 0; i < words.length; ++i) words[i] = dictionary.get(i);
        //建树过程
        for(String word : words){
            insert(root, word);
        }
        String[] strs = sentence.split(" ");
        for(int i = 0; i < strs.length; ++i){
            //如果可以在树中找到对应单词的前缀，那么将这个单词替换为它的前缀
            if(search(root, strs[i])){
                strs[i] = replace(strs[i], root);
            }
        }
        //用StringBuilder来把字符串数组还原成原字符串句子的转换目标字符串
        StringBuilder sb = new StringBuilder();
        for(String s : strs){
            sb.append(s).append(" ");
        }
        sb.deleteCharAt(sb.length()-1);
        return sb.toString();
    }
    //建前缀树模版
    public void insert(TrieNode root, String s){
        TrieNode node = root;
        for(char ch : s.toCharArray()){
            if(node.kids[ch - 'a'] == null) node.kids[ch - 'a'] = new TrieNode();
            node = node.kids[ch - 'a'];
        }
        node.isValid = true;
    }
    //查询是否存在传入的字符串的前缀
    public boolean search(TrieNode root, String s){
        TrieNode node = root;
        for(char ch : s.toCharArray()){
            if(node.isValid == true) break;
            if(node.kids[ch - 'a'] == null) return false;
            node = node.kids[ch - 'a'];
        }
        return true;
    }
    //将传入的字符串替换为它在前缀树中的前缀字符串
    public String replace(String s, TrieNode root){
        TrieNode node = root;
        StringBuilder sb = new StringBuilder();
        for(char ch : s.toCharArray()){
            if(node.isValid || node.kids[ch - 'a'] == null) break;
            node = node.kids[ch - 'a'];
            sb.append(ch);
        }
        return sb.toString();
    }
}

统计信息

通过次数	提交次数	AC比率
2405	3332	72.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言