648. Replace Words

Tags: ‘Hash Table’, ‘Trie’

In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can 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:

The input will only have lower-case letters.
1 <= dict words number <= 1000
1 <= sentence words number <= 1000
1 <= root length <= 100
1 <= sentence words length <= 1000

Solution

方法1：trie标准用法 49% 75%

class Solution {
    public String replaceWords(List<String> dict, String sentence) {
        Trie trie = new Trie();
        for (String word: dict) {
            trie.insert(word);
        }
        
        StringBuilder sb = new StringBuilder();
        String[] words = sentence.split("\\s+");
        for (String word: words) {
            sb.append(trie.findShortestPrefixWord(word) + " ");
        }
        
        return sb.toString().trim();
    }
    
    private class Node {
        private Node[] children;
        private boolean isWord;
        private String word;
        private Node() {
            children = new Node[26];
        }
    }
    
    private class Trie {
        private Node root;
        private Trie() {
            root = new Node();
        }
        
        private void insert(String word) {
            Node p = root;
            for (int i = 0; i < word.length(); i++) {
                int index = (int)(word.charAt(i) - 'a');
                if (p.children[index] == null) {
                    p.children[index] = new Node();
                }
                p = p.children[index];
            }
            p.isWord = true;
            p.word = word;
        }
        
        private String findShortestPrefixWord(String word) {
            Node p = root;
            for (int i = 0; i < word.length(); i++) {
                int index = (int)(word.charAt(i) - 'a');
                if (p.children[index] == null) {
                    break;
                }
                
                if (p.children[index].isWord) {
                    return p.children[index].word;
                }
                
                p = p.children[index];
            }
            return word;
        }
    }
}

Alex Blog

648. Replace Words