## Wednesday, May 2, 2018

### LeetCode 676 - Implement Magic Dictionary

https://leetcode.com/problems/implement-magic-dictionary/description/
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: Null
Input: search("hello"), Output: False
Input: search("hhllo"), Output: True
Input: search("hell"), Output: False
Input: search("leetcoded"), Output: False

Note:
1. You may assume that all the inputs are consist of lowercase letters a-z.
2. For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.
3. Please remember to RESET your class variables declared in class MagicDictionary, as static/class variables are persisted across multiple test cases. Please see here for more details.

https://leetcode.com/problems/implement-magic-dictionary/discuss/107454/Python-without-*26-factor-in-complexity
Let's say a word 'apple' has generalized neighbors '*pple', 'a*ple', 'ap*le', 'app*e', and 'appl*'. When searching for whether a word like 'apply' has a neighbor like 'apple', we only need to know whether they have a common generalized neighbor.
Continuing the above thinking, one issue is that 'apply' is not a neighbor with itself, yet it has the same generalized neighbor '*pply'. To remedy this, we'll count how many sources generated '*pply'. If there are 2 or more, then one of them won't be 'apply'. If there is exactly one, we should check that it wasn't 'apply'. In either case, we can be sure that there was some magic word generating '*pply' that wasn't 'apply'.
• Time Complexity: $O(\sum w_i^2)$ to build and $O(K^2)$ to search, where $w_i$ is the length of words[i], and $K$is the length of our search word.
• Space Complexity: $O(\sum w_i^2)$, the space used by count. We also use $O(K^2)$ space when generating neighbors to search.
    Set<String> words;
Map<String, Integer> count;

public MagicDictionary() {
words = new HashSet();
count = new HashMap();
}

private ArrayList<String> generalizedNeighbors(String word) {
ArrayList<String> ans = new ArrayList();
char[] ca = word.toCharArray();
for (int i = 0; i < word.length(); ++i) {
char letter = ca[i];
ca[i] = '*';
String magic = new String(ca);
ca[i] = letter;
}
return ans;
}

public void buildDict(String[] words) {
for (String word: words) {
for (String nei: generalizedNeighbors(word)) {
count.put(nei, count.getOrDefault(nei, 0) + 1);
}
}
}

public boolean search(String word) {
for (String nei: generalizedNeighbors(word)) {
int c = count.getOrDefault(nei, 0);
if (c > 1 || c == 1 && !words.contains(word)) return true;
}
return false;
}

X.
// len->
private Map<Integer, TreeSet<String>> 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 word : dict) {
}
}

/**
* 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) {
if (!map.containsKey(word.length())) {
return false;
}

TreeSet<String> set = map.get(word.length());
// <
String floor = set.lower(word);
char[] charArray = word.toCharArray();
if (floor != null && isDistanceOne(charArray, floor.toCharArray())) {
return true;
}

// >
String ceil = set.higher(word);
if (ceil != null && isDistanceOne(charArray, ceil.toCharArray())) {
return true;
}
return false;
}

// hello, hello should return false;
private boolean isDistanceOne(char[] word1, char[] word2) {
if (word1.length != word2.length)
return false;
int diff = 0;

for (int i = 0; i < word1.length; i++) {
if (word1[i] != word2[i]) {
diff++;
if (diff >= 2)
return false;
}
}
// BUG: not return true;
return diff == 1;

}

X. Using Trie
https://leetcode.com/problems/implement-magic-dictionary/discuss/107457/Java-implementation-using-Trie

This solution beats 93.56% java solutions.
https://leetcode.com/problems/implement-magic-dictionary/discuss/107465/Efficient-Trie-and-Java-8-w-Explanation
        Trie trie;
public MagicDictionary() {
trie = new Trie(256);
}

public void buildDict(String[] dict) {
Arrays.stream(dict).forEach(s -> trie.insert(s));
}

public boolean search(String word) {
return trie.relaxedSearch(word);
}

class Trie {
private int R;
private TrieNode root;

public Trie(int R) {
this.R = R;
root = new TrieNode();
}

public boolean relaxedSearch(String word) {
return relaxedSearch(root, word, 0);
}

private boolean relaxedSearch(TrieNode root, String word, int changedTimes) {
if (root == null || (!root.isWord && word.isEmpty()) || changedTimes > 1) return false;
if (root.isWord && word.isEmpty()) return changedTimes == 1;
return Arrays.stream(root.next).anyMatch(nextNode -> relaxedSearch(nextNode, word.substring(1),
root.next[word.charAt(0)] == nextNode ? changedTimes : changedTimes+1));
}

// Inserts a word into the trie.
public void insert(String word) {
insert(root, word);
}

private void insert(TrieNode root, String word) {
if (word.isEmpty()) { root.isWord = true; return; }
if (root.next[word.charAt(0)] == null) root.next[word.charAt(0)] = new TrieNode();
insert(root.next[word.charAt(0)], word.substring(1));
}

private class TrieNode {
private TrieNode[] next = new TrieNode[R];
private boolean isWord;
}

}
https://leetcode.com/problems/implement-magic-dictionary/discuss/107453/Easiest-JAVA-with-Trie-no-need-to-count-the-number-of-changes
First build a trie tree, and in search(String word) function, we just edit every character from 'a' to 'z' and search the new string.
(This process is like "word ladder")

if k is the average length of input string, you are using O(nk) for building the Trie and O(26k^2) for searching the Trie.. That's a really bad application for Trie.
If you really want to iterate all 26 alphabet possibilities (which is unnecessary), why don't you just use a HashSet. so O(n) for building the set and O(26
k) for searching?
    class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isWord;
public TrieNode() {}
}
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 s : dict) {
TrieNode node = root;
for (char c : s.toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.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) {
char[] arr = word.toCharArray();
for (int i = 0; i < word.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
if (arr[i] == c) {
continue;
}
char org = arr[i];
arr[i] = c;
if (helper(new String(arr), root)) {
return true;
}
arr[i] = org;
}
}
return false;
}
public boolean helper(String s, TrieNode root) {
TrieNode node = root;
for (char c : s.toCharArray()) {
if (node.children[c - 'a'] == null) {
return false;
}
node = node.children[c - 'a'];
}
return node.isWord;
}

• Time Complexity: $O(S)$ to build and $O(NK)$ to search, where $N$ is the number of words in our magic dictionary, $S$ is the total number of letters in it, and $K$ is the length of the search word.
• Space Complexity: $O(S)$, the space used by buckets.
class MagicDictionary {
Map<Integer, ArrayList<String>> buckets;
public MagicDictionary() {
buckets = new HashMap();
}

public void buildDict(String[] words) {
for (String word: words) {
}
}

public boolean search(String word) {
if (!buckets.containsKey(word.length())) return false;
for (String candidate: buckets.get(word.length())) {
int mismatch = 0;
for (int i = 0; i < word.length(); ++i) {
if (word.charAt(i) != candidate.charAt(i)) {
if (++mismatch > 1) break;
}
}
if (mismatch == 1) return true;
}
return false;
}