Trie used Python solution O(m^2 n^2), O(1)


  • 0
    F
    class Solution(object):
        def findWords(self, board, words):
            """
            :type board: List[List[str]]
            :type words: List[str]
            :rtype: List[str]
            """
            def DFS(path, i, j, trie):
                if '#' in trie:
                    rst.add(path)
                    
                if i < 0 or j < 0 or i > m - 1 or j > n - 1 or board[i][j] not in trie:
                    return
                tmp = board[i][j]
                board[i][j] = ord(tmp) ^ 256
                for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
                    DFS(path + tmp, x,  y, trie[tmp])
                board[i][j] = tmp 
                
            if not board: return []
            trie = {}
            for word in words:
                t = trie
                for w in word:
                    if w not in t:
                        t[w] = {}
                    t = t[w]
                t['#'] = '#'
            rst = set()
            m, n = len(board), len(board[0])
            for i in xrange(m):
                for j in xrange(n):
                    DFS("", i, j, trie)
            return list(rst)
    

  • 0
    S

    What does "board[i][j] = ord(tmp) ^ 256" do?


  • 0
    R

    @Skywalker-lili
    It marks board[i][j] visited. Using anything other than lowercase letters will also work. I don't know he chose xor though.


Log in to reply
 

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