648 Replace Words

648. Replace Words

1. Question

In English, we have a concept calledroot, which can be followed by some other words to form another longer word - let's call this wordsuccessor. For example, the rootan, followed byother, which can form another wordanother.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all thesuccessorin the sentence with therootforming it. If asuccessorhas manyrootscan form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"

Output: "the cat was rat by the bat"

Note:

1. The input will only have lower-case letters.

2. 1 <= dict words number <= 1000

3. 1 <= sentence words number <= 1000

4. 1 <= root length <= 100

5. 1 <= sentence words length <= 1000

2. Implementation

(1) Trie

思路: 很典型的查询prefix的应用，所以用trie很适合，只要在trieNode的基础上加入字典里的string所对应的index即可

class Solution {
    class TrieNode {
        char val;
        int index;
        boolean isWord;
        TrieNode[] childNode;

        public TrieNode(char val) {
            this.val = val;
            index = -1;
            childNode = new TrieNode[26];
        }
    }

    class Trie {
        TrieNode root;

        public Trie() {
            root = new TrieNode(' ');
        }

        public void insert(String word, int index) {
            if (word == null || word.length() == 0) {
                return;
            }

            TrieNode curNode = root;

            for (char c : word.toCharArray()) {
                int pos = c - 'a';
                if (curNode.childNode[pos] == null) {
                    curNode.childNode[pos] = new TrieNode(c);
                }
                curNode = curNode.childNode[pos];
            }
            curNode.isWord = true;
            curNode.index = index;
        }

        public int searchPrefix(String word) {
            if (word == null || word.length() == 0) {
                return -1;
            }

            TrieNode curNode = root;

            for (char c : word.toCharArray()) {
                int pos = c - 'a';
                if (curNode.childNode[pos] == null) {
                    return -1;
                }
                else if (curNode.childNode[pos].isWord){
                    return curNode.childNode[pos].index;
                }
                curNode = curNode.childNode[pos];
            }
            return curNode.index;
        }
    }
    public String replaceWords(List<String> dict, String sentence) {
        if (dict.size() == 0 || sentence == null || sentence.length() == 0) {
            return "";
        }

        Trie trie = new Trie();

        for (int i = 0; i < dict.size(); i++) {
            trie.insert(dict.get(i), i);
        }

        String[] words = sentence.split("\\s+");

        for (int i = 0; i < words.length; i++) {
            int index = trie.searchPrefix(words[i]);

            if (index != -1) {
                words[i] = dict.get(index);
            }
        }

        StringBuilder res = new StringBuilder();

        for (int i = 0; i < words.length - 1; i++) {
            res.append(words[i]);
            res.append(" ");
        }

        res.append(words[words.length - 1]);
        return res.toString();
    }
}

3. Time & Space Complexity

Trie: 时间复杂度O(n * m), n是dict里面string的个数，m是string的平均长度。 空间复杂度O(nm)