## Google Interview Question

Software Developers**Country:**United States

**Interview Type:**In-Person

An alternative O(n*n) solution would be to preprocess the dictionary into a hash map thus: for every dictionary word w of length q add q words to the hashmap which can be created by removing q-th letter from the word w. Example: for the word 'dog' we add 'og', 'dg', 'do' into the hashmap. Then for the input word we do a similar thing: remove i-th letter and see if the resultant word is in the hashmap. It's quadratic because it takes O(n) to hash the word and we need to do it n times.

```
D = ['apple', 'apple', 'banana', 'orange']
def preprocess_dict():
hmap = set()
for word in D:
for i in range(len(word)):
hmap.add(word[:i] + word[i+1:])
return hmap
H = preprocess_dict()
def word_exists(word):
for i in range(len(word)):
if (word[:i] + word[i+1:]) in H:
return True
return False
print (word_exists('aPple'))
```

Preprocess the dictionary into a trie. On every iteration we will have letter z of the input word and set S comprising of pairs (x,r) where x indicates our non-matching character allowance, and r is a trie node. Initially we put (1,R) to S, where R is the trie root node. For every node (x,r) in S and every child node w of r we put (x,w) back to S if w corresponds to z; otherwise we put (x-1,w) provided that x>0. Terminate when an end-of-word child node is encountered meaning we found a match. Complexity: quadratic worst case. This is because on every iteration the increment of the size of S is bounded by constant L (the length of the alphabet), as entries with x==0 can only 'spawn' at most 1 new entry in place of itself and at every point there is only 1 entry with x==1 which can spawn at most L new entries (with x==0) giving us O(n*n*L) = O(n*n).

- adr October 02, 2019