删除给定字符串的一个字符之后，能否在字典中找到删除一个字符之后相等的值
问题：
Implement a magic directory with buildDict, and search methods.
For the method buildDict, you'll be given a list of non-repetitive words to build a dictionary.
For the method search, you'll be given a word, and judge whether if you modify exactly one character into another character in this word, the modified word is in the dictionary you just built.
Example 1:
Input: buildDict(["hello", "leetcode"]), Output: NullInput: search("hello"), Output: FalseInput: search("hhllo"), Output: TrueInput: search("hell"), Output: FalseInput: search("leetcoded"), Output: False Note:
- You may assume that all the inputs are consist of lowercase letters
a-z. - For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.
- Please remember to RESET your class variables declared in class MagicDictionary, as static/class variables are persisted across multiple test cases. Please see for more details.
解决：
①
- 对于字典中的每个单词，每个字符，删除字符并将单词的其余部分作为关键字，将删除的字符和字符的下标作为值列表的一部分放入map中。
- 例如：“hello” -> {“ello”:[[0, ‘h’]], “hllo”:[[1, ‘e’]], “helo”:[[2, ‘l’],[3, ‘l’]], “hell”:[[4, ‘o’]]}
- 在查找过程中，如步骤1所示生成key。当键值对中有一对相同的index但char不同时，返回true。 例如“healo”当删除一个键时，键是“helo”，并且有一个索引相同但char不同的[2，'l']，则返回true。
class MagicDictionary { //141ms
Map<String,List<int[]>> map = new HashMap<>(); /** Initialize your data structure here. */ public MagicDictionary() {} /** Build a dictionary through a list of words */ public void buildDict(String[] dict) { for (String s : dict){ for (int i = 0;i < s.length();i ++){ String key = s.substring(0,i) + s.substring(i + 1); int[] pair = new int[]{i,s.charAt(i)}; List<int[]> val = map.getOrDefault(key,new ArrayList<>()); val.add(pair); map.put(key,val); } } } /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */ public boolean search(String word) { for (int i = 0;i < word.length();i ++){ String key = word.substring(0,i) + word.substring(i + 1); if (map.containsKey(key)){ for (int[] pair : map.get(key)){ if (pair[0] == i && pair[1] != word.charAt(i)){ return true; } } } } return false; } } /** * Your MagicDictionary object will be instantiated and called as such: * MagicDictionary obj = new MagicDictionary(); * obj.buildDict(dict); * boolean param_2 = obj.search(word); */② 使用前缀树实现。
class MagicDictionary { //106ms
class TrieNode{ TrieNode[] children = new TrieNode[26]; boolean isWord = false; } TrieNode root; /** Initialize your data structure here. */ public MagicDictionary() { root = new TrieNode(); } /** Build a dictionary through a list of words */ public void buildDict(String[] dict) { for (String word : dict){ TrieNode cur = root; for (char c : word.toCharArray()){ int i = c - 'a'; if (cur.children[i] == null) cur.children[i] = new TrieNode(); cur = cur.children[i]; } cur.isWord = true; } } /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */ public boolean search(String word) { return search(root,word.toCharArray(),0,0); } public boolean search(TrieNode root,char[] word,int start,int changed){ if (start == word.length) return root.isWord && changed == 1; int index = word[start] - 'a'; for (int i = 0;i < 26;i ++){ if (root.children[i] == null) continue; if (i == index){ if (search(root.children[i],word,start + 1,changed)) return true; }else { if (changed == 0 && search(root.children[i],word,start + 1,changed + 1)) return true; } } return false; } } /** * Your MagicDictionary object will be instantiated and called as such: * MagicDictionary obj = new MagicDictionary(); * obj.buildDict(dict); * boolean param_2 = obj.search(word); */