# 3 Python Solutions with very detailed explanations

• Solution with discussion https://discuss.leetcode.com/topic/73514/3-python-solutions-with-very-detailed-explanations

Word Squares https://leetcode.com/problems/word-squares/

• All words are equal length. So the dimensions of a word square will be len(word[0])
• Now our approach will be to incrementally build a solution. The solution built will be kept in so_far array. This buildup of the solution will follow a general backtracking template - process_solution and generate_candidates.
• generate_candidates will produce prefix using the so_far array. Now the next word that can be added to the so_far array must have this prefix. Check the visual in this link to understand this better: https://discuss.leetcode.com/topic/63516/explained-my-java-solution-using-trie-126ms-16-16
``````class Solution(object):
def generate_candidates(self, so_far, words):
prefix =  "".join([x[len(so_far)] for x in so_far])
for w in words:
if w.startswith(prefix):
yield w

def helper(self, so_far, N, words, results):
if len(so_far) == N:
results.append([x for x in so_far])
else:
for c in self.generate_candidates(so_far, words):
so_far.append(c)
self.helper(so_far, N, words, results)
so_far.pop()
return

def wordSquares(self, words):
"""
:type words: List[str]
:rtype: List[List[str]]
"""
results = []
if words:
self.helper([], len(words[0]), words, results)
return results
``````

Optimized solution using Hash-Tables

• In the previous brute force solution, the bottle-neck was that we had to linearly scan all the words to filter those words which start with a prefix.
• What if we pre-process all words and store in a hash table. The key would be the prefix and value would be the list of words with that prefix.
• Then we can lookup all words with a prefix in constant time!
• We implement a new class called PrefixHashTable and store a mapping of all prefixes to words in it.
``````class PrefixHashTable(object):
def __init__(self, words):
self.prefix_table = {}
for w in words:
for prefix in (w[0:i] for i in range(len(w))):
return

def get_prefix_matches(self, prefix):
candidates = self.prefix_table[prefix] if prefix in self.prefix_table else set([])
return candidates

class Solution(object):
def helper(self, so_far, N, words, results, table):
if len(so_far) == N:
results.append([x for x in so_far])
else:
prefix = "".join([x[len(so_far)] for x in so_far])
for c in table.get_prefix_matches(prefix):
so_far.append(c)
self.helper(so_far, N, words, results, table)
so_far.pop()
return

def wordSquares(self, words):
"""
:type words: List[str]
:rtype: List[List[str]]
"""
results = []
if words:
table = PrefixHashTable(words)
self.helper([], len(words[0]), words, results, table)
return results
``````

Optimized solution using Tries

• Prefix matching can also be done using Tries.
• We implement a simple Trie and encapsulate it within the PrefixTrie API.
``````class TrieNode(object):
def __init__(self, value):
self.nxt = [None]*26
self.value = value
return

class PrefixTrieTable(object):
def __init__(self, words):
self.root = TrieNode(None)
for w in words:
return

root = self.root
for ch in w:
offset = ord(ch)-ord('a')
if root.nxt[offset] != None:
root = root.nxt[offset]
else:
root.nxt[offset] = TrieNode(None)
root = root.nxt[offset]
root.value = w
return

def collect(self, root, candidates):
if root.value:
candidates.append(root.value)
else:
for i in range(26):
if root.nxt[i]:
self.collect(root.nxt[i], candidates)
return

def get_prefix_matches(self, prefix):
candidates, root = [], self.root
for ch in prefix:
offset = ord(ch)-ord('a')
root = root.nxt[offset]
if root == None:
return candidates
self.collect(root, candidates)
return candidates

class Solution(object):
def helper(self, so_far, N, words, results, table):
if len(so_far) == N:
results.append([x for x in so_far])
else:
prefix = "".join([x[len(so_far)] for x in so_far])
for c in table.get_prefix_matches(prefix):
so_far.append(c)
self.helper(so_far, N, words, results, table)
so_far.pop()
return

def wordSquares(self, words):
"""
:type words: List[str]
:rtype: List[List[str]]
"""
results = []
if words:
table = PrefixTrieTable(words)
self.helper([], len(words[0]), words, results, table)
return results
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.