Backtracking for words related problems

For the words related problems, we can usually solve it by backtracking or DFS. Sometimes, in order to make the process more efficient, we can use Trie or prefix hash map.

LeetCode 425. Word Squares

For this problem, we can use both the prefix hash map and trie.

A critical observation is shown as follows:

Each time, the yellow one will be the needed prefix during the building process.

Image is from HERE

Solution based on prefix hash map in python

class Solution:
    def _build_prefix_hash_table(self):
        for word in self.words:
            for i in range(len(word)):
                self.prefix_hash_table[word[:i+1]].add(word) 
                
    def wordSquares(self, words: List[str]) -> List[List[str]]:
        self.N = len(words[0])
        self.words = words
        self.prefix_hash_table =  collections.defaultdict(set)
        self._build_prefix_hash_table()
        
        ret = []
        # backtracking to build the word square
        def backtracking(curr):
            if len(curr)== self.N:
                ret.append(curr)
                return
            j = len(curr)
            next_prefix = ''.join([w[j] for w in curr])
            for word in self.prefix_hash_table[next_prefix]:
                backtracking(curr+[word])
                       
        for word in words:
            backtracking([word])
        return ret

Reference

https://leetcode.com/problems/word-squares/discuss/91333/Explained.-My-Java-solution-using-Trie-126ms-1616