Python DFS Solution, beat 97%


  • 0
    A

    Typical idea using Trie and DFS

    class TrieNode():
        def __init__(self):
            self.children = dict()
            self.word = ""
    
    class Trie():
        def __init__(self):
            self.root = TrieNode()
    
        def add(self, word):
            node = self.root
            for letter in word:
                if node.children.has_key(letter):
                    node = node.children[letter]
                else:
                    node.children[letter] = TrieNode()
                    node = node.children[letter]
            node.word = word
    
    class Solution(object):
        def findWords(self, G, words):
            m = len(G)
            if m == 0: return []
            n = len(G[0])
            if n == 0: return []
            result = set()
            # initialize a trie tree
            trie = Trie()
            for w in words:
                trie.add(w)
            # search
            root = trie.root
            for i in xrange(m):
                for j in xrange(n):
                    letter = G[i][j]
                    if letter in root.children:
                        self.DFS(G, root.children[letter], i, j, result)
            return list(result)
    
        def DFS(self, G, node, i, j, res):
            if node.word != "":
                res.add(node.word)
            if node.children is None:
                return
            m, n = len(G), len(G[0])
            back = G[i][j]
            G[i][j] = '*'
            if i-1 >= 0 and G[i-1][j] in node.children:
                self.DFS(G, node.children[G[i-1][j]], i-1, j, res)
            if i+1 < m and G[i+1][j] in node.children:
                self.DFS(G, node.children[G[i+1][j]], i+1, j, res)
            if j-1 >= 0 and G[i][j-1] in node.children:
                self.DFS(G, node.children[G[i][j-1]], i, j-1, res)
            if j+1 < n and G[i][j+1] in node.children:
                self.DFS(G, node.children[G[i][j+1]], i, j+1, res)
            G[i][j] = back
    

    If I change DFS helper function into following, the runtime will be doubled...

        def DFS(self, G, node, i, j, res):
            if node.word != "":
                res.add(node.word)
            if len(node.children) == 0:
                return
            m, n = len(G), len(G[0])
            dir = [(-1, 0), (1, 0), (0, 1), (0, -1)]
            back = G[i][j]
            G[i][j] = '*'
            for dx, dy in dir:
                x, y = i + dx, j + dy
                if x < 0 or x >= m or y < 0 or y >= n:
                    continue
                letter = G[x][y]
                if letter in node.children:
                    self.DFS(G, node.children[letter], x, y, res)
            G[i][j] = back
    

Log in to reply
 

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