648. Replace Words

题目描述和难度

题目描述：

在英语中，我们有一个叫做 词根(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

题目难度：中等。
英文网址：648. Replace Words 。
中文网址：648. 单词替换。

思路分析

求解关键：

参考解答

参考解答1

import java.util.Arrays;
import java.util.List;

public class Solution {

    // 我自己写的代码，实现了一个字典树 Trie

    private class Trie {

        private Node root;

        private class Node {
            private Node[] next;
            private boolean isEnd;

            public Node() {
                this.next = new Node[26];
                this.isEnd = false;
            }
        }

        public Trie() {
            root = new Node();
        }

        /**
         * insert 方法和一半前缀树无异
         *
         * @param word
         */
        public void insert(String word) {
            Node curNode = root;
            for (char c : word.toCharArray()) {
                if (curNode.next[c - 'a'] == null) {
                    curNode.next[c - 'a'] = new Node();
                }
                curNode = curNode.next[c - 'a'];
            }
            if (!curNode.isEnd) {
                curNode.isEnd = true;
            }
        }

        /**
         * @param word 词根
         * @return 如果是词根，则返回到词根的索引值（不包含该索引），如果不是词根，返回 0
         */
        public int startsWith(String word) {
            int index = 0;
            Node curNode = root;
            for (char c : word.toCharArray()) {
                if (curNode.next[c - 'a'] == null) {
                    return 0;
                }
                curNode = curNode.next[c - 'a'];
                index++;
                if (curNode.isEnd) {
                    return index;
                }
            }
            // 如果是前缀，则返回 0 ，例如：字典里面是 hello，而遍历的单词是 he
            return 0;
        }
    }

    public String replaceWords(List<String> dict, String sentence) {
        if (dict == null || dict.size() == 0 || sentence == null || sentence.length() == 0) {
            return "";
        }
        Trie trie = new Trie();
        for (String word : dict) {
            trie.insert(word);
        }

        StringBuilder stringBuilder = new StringBuilder();
        for (String word : sentence.split(" ")) {
            int index = trie.startsWith(word);
            if (index == 0) {
                stringBuilder.append(word);
            } else {
                stringBuilder.append(word.substring(0, index));
            }
            stringBuilder.append(" ");
        }
        // 删除最后一个空格
        stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> dict = Arrays.asList(new String[]{"cat", "bat", "rat"});
        String sentence = "the cattle was rattled by the battery";
        String replaceWords = solution.replaceWords(dict, sentence);
        System.out.println(replaceWords);
    }
}

参考解答2

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution2 {

    public String replaceWords(List<String> dict, String sentence) {
        Set<String> set = new HashSet<>();
        set.addAll(dict);
        StringBuilder stringBuilder = new StringBuilder();

        String[] words = sentence.split(" ");
        int len = words.length;
        for (int i = 0; i < len; i++) {
            for (int j = 1; j <= words[i].length(); j++) {
                String prefix = words[i].substring(0, j);
                if (set.contains(prefix)) {
                    words[i] = prefix;
                    break;
                }
            }
            stringBuilder.append(words[i]);
            stringBuilder.append(" ");
        }
        return stringBuilder.substring(0, stringBuilder.length() - 1);
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        List<String> dict = Arrays.asList(new String[]{"cat", "bat", "rat"});
        String sentence = "the cattle was rattled by the battery";
        String replaceWords = solution2.replaceWords(dict, sentence);
        System.out.println(replaceWords);
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0648-replace-words ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。