Sword finger offer II 064. magic Dictionary (medium dictionary tree string design)

The finger of the sword Offer II 064. Magic dictionary

Design a data structure initialized with word list , Words in the word list Different from each other . If you give a word , Please decide whether you can replace only one letter of this word with another , Make the new words exist in the built magic Dictionary .

Realization MagicDictionary class ：

MagicDictionary() Initialize object
void buildDict(String[] dictionary) Use string arrays dictionary Set the data structure ,dictionary Strings in are different from each other
bool search(String searchWord) Given a string searchWord , Determine whether you can only put... In the string One Replace one letter with another , So that the new string formed can match any string in the dictionary . If possible , return true ; otherwise , return false .

Example ：

Input
inputs = [“MagicDictionary”, “buildDict”, “search”, “search”, “search”, “search”]
inputs = [[], [[“hello”, “leetcode”]], [“hello”], [“hhllo”], [“hell”], [“leetcoded”]]
Output
[null, null, false, true, false, false]

explain
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict([“hello”, “leetcode”]);
magicDictionary.search(“hello”); // return False
magicDictionary.search(“hhllo”); // Put the second ‘h’ Replace with ‘e’ Can match “hello” , So back True
magicDictionary.search(“hell”); // return False
magicDictionary.search(“leetcoded”); // return False

Tips ：

1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
dictionary[i] It's only made up of lowercase letters
dictionary All the strings in Different from each other
1 <= searchWord.length <= 100
searchWord It's only made up of lowercase letters
buildDict Only in search Before calling once
Call at most 100 Time search

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

analysis

First, construct prefix tree , Put the words in the dictionary into the prefix tree , And then use it dfs Search all the letters of the target word , Yes 26 Judge every letter , Use a variable cnt Record the number of letter substitutions , If the replacement is more than one letter, it returns false,dfs Backtracking will jump to the judgment of the next letter .

Answer key （Java）

class MagicDictionary {
    
    static class TrieNode {
    
        public TrieNode[] children;
        public boolean isWord;

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

    private TrieNode root;

    /** Initialize your data structure here. */
    public MagicDictionary() {
    
        root = new TrieNode();
    }
    
    public void buildDict(String[] dictionary) {
    // Put the words of the dictionary into the prefix tree 
        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;
        }
    }
    
    public boolean search(String searchWord) {
    
        return dfs(root, searchWord, 0, 0);
    }

    private boolean dfs(TrieNode root, String searchWord, int i, int cnt) {
    
        if (root == null) {
    // The current letter does not exist in the tree 
            return false;
        }

        if (root.isWord && i == searchWord.length() && cnt == 1) {
    // After a replacement, the target word is the word in the tree 
            return true;
        }

        if (i < searchWord.length() && cnt < 2) {
    
            boolean found = false;
            for (int j = 0; j < 26 && !found; j++) {
    
            //found yes true There is no need to judge the subsequent letters 
                int next = j == searchWord.charAt(i) - 'a' ? cnt : cnt + 1;
                found = dfs(root.children[j], searchWord, i + 1, next);
            }
            return found;
        }
        return false;
    }
}

/** * Your MagicDictionary object will be instantiated and called as such: * MagicDictionary obj = new MagicDictionary(); * obj.buildDict(dictionary); * boolean param_2 = obj.search(searchWord); */