425.Word Squares
Tags: [trick], [tree], [trie], [prefix_tree], [prefix], [DFS], [permutation], [preprocessing]
Com: {g}
Link: https://leetcode.com/problems/word-squares/#/description
Given a set of words(without duplicates), find all word squares you can build from them.
A sequence of words forms a valid word square if thekthrow and column read the exact same string, where 0 ≤k< max(numRows, numColumns).
For example, the word sequence["ball","area","lead","lady"]forms a word square because each word reads the same both horizontally and vertically.
b a l l
a r e a
l e a d
l a d y
Note:
- There are at least 1 and at most 1000 words.
- All words will have the exact same length.
- Word length is at least 1 and at most 5.
- Each word contains only lowercase English alphabet
a-z.
Example 1:
Input:
["area","lead","wall","lady","ball"]
Output:
[
[ "wall",
"area",
"lead",
"lady"
],
[ "ball",
"area",
"lead",
"lady"
]
]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).
Example 2:
Input:
["abat","baba","atan","atal"]
Output:
[
[ "baba",
"abat",
"baba",
"atan"
],
[ "baba",
"abat",
"baba",
"atal"
]
]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).
Better Solution: Preprocessing
class Solution(object):
def wordSquares(self, words):
"""
:type words: List[str]
:rtype: List[List[str]]
"""
if not words:
return []
word_len = len(words[0])
prefixes = collections.defaultdict(set)
for w in words:
for sub_len in xrange(1, word_len + 1):
prefix = w[:sub_len]
prefixes[prefix].add(w)
result = []
buff = []
for w in words:
buff.append(w)
self.helper(prefixes, word_len, buff, result)
buff.pop()
return result
def helper(self, prefixes, word_len, buff, result):
# base case
if len(buff) == word_len:
result.append(list(buff))
return
prefix_buff = []
for w in buff:
prefix_buff.append(w[len(buff)])
prefix = ''.join(prefix_buff)
candidates = prefixes[prefix]
for c in candidates:
buff.append(c)
self.helper(prefixes, word_len, buff, result)
buff.pop()
Revelation:
- The main logic is as same as the PrefixTree solution, but here we do preprocessing to precompute all prefixes and put them into a map, then latter, we can query the prefix very fast.
Note:
- Time complexity = O(n * word_len + n * n^word_len), n is the number of words.
Solution: Trie, Prefix Tree
class Solution(object):
class PrefixTree(object):
class TreeNode(object):
def __init__(self, val):
self.val = val
self.end_of_w = False
self.children = []
def __init__(self, words):
self.root = self.TreeNode('')
for w in words:
self.insert_word(self.root, w, 0)
def insert_word(self, root, word, index):
curr_c = word[index]
target = None
for child in root.children:
if child.val == curr_c:
target = child
break
if not target:
target = self.TreeNode(curr_c)
root.children.append(target)
if index == len(word) - 1:
target.end_of_w = True
else:
self.insert_word(target, word, index + 1)
def search(self, prefix):
if not prefix:
return []
result = []
buff = []
self.search_helper(self.root, prefix, 0, buff, result)
return result
def search_helper(self, root, prefix, index, buff, result):
# base case
if index == len(prefix) - 1:
target = None
for child in root.children:
if child.val == prefix[-1]:
target = child
break
if target:
self.dfs(target, buff, result)
return
curr_c = prefix[index]
target = None
for child in root.children:
if child.val == curr_c:
target = child
break
if target:
buff.append(curr_c)
self.search_helper(target, prefix, index + 1, buff, result)
def dfs(self, root, buff, result):
buff.append(root.val)
if root.end_of_w:
result.append(''.join(buff))
for child in root.children:
self.dfs(child, buff, result)
buff.pop()
def wordSquares(self, words):
"""
:type words: List[str]
:rtype: List[List[str]]
"""
if not words:
return 0
prefix_tree = self.PrefixTree(words)
w_sq_size = len(words[0])
result = []
buff = []
for w in words:
buff.append(w)
self.helper(prefix_tree, buff, w_sq_size, result)
buff.pop()
return result
def helper(self, prefix_tree, buff, w_sq_size, result):
# base case
if len(buff) == w_sq_size:
result.append(list(buff))
return
prefix_buff = []
curr_num_of_w = len(buff)
for w in buff:
prefix_buff.append(w[curr_num_of_w])
prefix = ''.join(prefix_buff)
candidates = prefix_tree.search(prefix)
for c in candidates:
buff.append(c)
self.helper(prefix_tree, buff, w_sq_size, result)
buff.pop()
Revelation:
- Build the word square step by step, row by row. We first choose one word as the first word, then using recursion to choose next word, because there exists the constraints, we can know the new word's prefix, so we just need a proper data structure to search the words based on prefix, and PrefixTree(Trie) is a proper data structure for this usage.
Note:
- Time complexity = O(len(words) * word_len + len(words) * len(words)^word_len * word_len).
Time Limited Exceeded: Permutation
class Solution(object):
def wordSquares(self, words):
"""
:type words: List[str]
:rtype: List[List[str]]
"""
if not words:
return []
word_sq_size = len(words[0])
result = []
buff = []
self.word_squares_helper(words, word_sq_size, buff, result)
return result
def word_squares_helper(self, words, word_sq_size, buff, result):
# base case
if len(buff) == word_sq_size:
if self.is_valid(buff):
result.append(list(buff))
return
for i in xrange(len(words)):
buff.append(words[i])
self.word_squares_helper(words, word_sq_size, buff, result)
buff.pop()
def is_valid(self, word_sq):
for row in xrange(len(word_sq)):
for col in xrange(len(word_sq[0])):
if word_sq[row][col] != word_sq[col][row]:
return False
return True
Revelation:
- Here we didn't use index_set, because the word cannot reused.
- Permutation: each level of recursion, we try all possible candidates, so there is no start index.
Note:
- Time complexity = O(n! * word_len^2), n is the number of words.