Sword finger offer II 063. replacement word (medium prefix tree string)

The finger of the sword Offer II 063. Replace words

In English , There's one called Root (root) The concept of , It can be followed by other words to form another longer word —— We call it Inheritance words (successor). for example , Root an, Follow the word other( other ), Can form new words another( the other one ).

Now? , Given a dictionary of many roots and a sentence , You need to replace all inherited words in the sentence with roots . If an inherited word has many roots that can form it , Replace it with the shortest root .

You need to output the sentence after 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”
Example 3：

Input ：dictionary = [“a”, “aa”, “aaa”, “aaaa”], sentence = “a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa”
Output ：“a a a a a a a a bbb baba a”
Example 4：

Input ：dictionary = [“catt”,“cat”,“bat”,“rat”], sentence = “the cattle was rattled by the battery”
Output ：“the cat was rat by the bat”
Example 5：

Input ：dictionary = [“ac”,“ab”], sentence = “it is abnormal that this solution is accepted”
Output ：“it is ab that this solution is ac”

Tips ：

1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 100
dictionary[i] It's only made up of lowercase letters .
1 <= sentence.length <= 10^6
sentence Only lowercase letters and spaces .
sentence The total number of words in the range [1, 1000] Inside .
sentence The length of each word in the range [1, 1000] Inside .
sentence Words in are separated by a space .
sentence No leading or trailing spaces .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/UhWRSj
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

The application of prefix tree .
This problem is obviously to use prefix tree , The last question is similar to , First, build the data structure of prefix tree , And then dictionary The string of is added to the prefix tree , Yes sentence Judge the words in , If the prefix of a word is in the prefix tree, the prefix string is returned , Replace current word , Otherwise, it returns empty , The current word does not change . It should be noted that , Used String Of join() Method , The first parameter of this method is the delimiter , The following parameters can be multiple strings separated by commas , It can also be the string array of this topic or the dynamic string array , Method is a string that connects all strings and adds a separator between them . Such as ：
String.join(“-”,“You”,“are”,“Awesome”) return "You-are-Awesome"

Answer key （Java）

class Solution {
    
    static class TrieNode {
    
        TrieNode children[];
        boolean isWord;

        public TrieNode() {
    
            children = new TrieNode[26];
        }
    }

    public String replaceWords(List<String> dictionary, String sentence) {
    
        TrieNode root = buildTrie(dictionary);
        String[] wordArray = sentence.split(" ");
        for (int i = 0; i < wordArray.length; i++) {
    
            String prefix = findPrefix(root, wordArray[i]);
            if (!"".equals(prefix)) {
    
                wordArray[i] = prefix;
            }
        }
        return String.join(" ", wordArray);
    }
    
    private TrieNode buildTrie(List<String> dictionary) {
    
        TrieNode root = new TrieNode();
        for (String word : dictionary) {
    
            TrieNode node = root;
            for (char ch : word.toCharArray()) {
    
                if (node.children[ch - 'a'] == null) {
    
                    node.children[ch - 'a'] = new TrieNode();
                }

                node = node.children[ch - 'a'];
            }
            node.isWord = true;
        }
        return root;
    }

    private String findPrefix(TrieNode root, String word) {
    
        TrieNode node = root;
        StringBuilder sb = new StringBuilder();
        for (char ch : word.toCharArray()) {
    
            if (node.isWord || node.children[ch - 'a'] == null) {
    
                break;
            }
            sb.append(ch);
            node = node.children[ch - 'a'];
        }
        return node.isWord ? sb.toString() : "";
    }
}