3 Python Solutions with very detailed explanations


  • 2
    G

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

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

    Backtracking with Incremental Addition

    • 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))):
                    self.prefix_table.setdefault(prefix, set([])).add(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:
                self.add_to_trie(w)
            return
        
        def add_to_trie(self, w):
            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
    

Log in to reply
 

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