648. Replace Words

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root that has the shortest length.

Return the sentence after the replacement.

Example 1:

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

Example 2:

Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"

Constraints:

• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 100
• dictionary[i] consists of only lower-case letters.
• $1 <= sentence.length <= 10^6$
• sentence consists of only lower-case letters and spaces.
• The number of words in sentence is in the range [1, 1000]
• The length of each word in sentence is in the range [1, 1000]
• Every two consecutive words in sentence will be separated by exactly one space.
• sentence does not have leading or trailing spaces.

Code

208. Implement Trie (Prefix Tree)

class Solution {
    class TrieNode {
        TrieNode[] children;
        boolean isWord;
        String word;

        public TrieNode() {
            children = new TrieNode[26];
            isWord = false;
            word = "";
        }
    }

    TrieNode root;
    public String replaceWords(List<String> dictionary, String sentence) {
        root = new TrieNode();

        for(String str : dictionary){
            insert(str);
        }

        String[] words = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for(String word : words) {
            String res = search(word);
            sb.append(res).append(" ");
        }

        return sb.toString().trim();
    }

    private String search(String word) {
        TrieNode node = root;

        for(int i = 0; i < word.length(); i++){
            int index = word.charAt(i) - 'a';
            TrieNode child = node.children[index];

            if(child != null && child.isWord) {
                return child.word;
            }

            if(child == null) return word;

            node = node.children[index];
        }

        return word;
    }

    private void insert(String word) {
        TrieNode node = root;

        for(int i = 0; i < word.length(); i++){
            int index = word.charAt(i) - 'a';
            if(node.children[index] == null){
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }

        node.isWord = true;
        node.word = word;
    }
}

• Time Complexity: O(N)
• Space Complexity: O(N)