212. Word Search II

Problem Link

Tutorial

Use trie to store all the words. Then we do a DFS on the board, at each step of which we check whether the current path is a prefix of some words using the trie as a prunning method.

Solution

class TrieNode:
    def __init__(self):
        self.isEnd=False
        self.children={}

    def insert(self,word):
        cur=self
        for i in word:
            if i not in cur.children:
                cur.children[i]=TrieNode()
            cur=cur.children[i]
        cur.isEnd=True


class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        trie = TrieNode()
        for word in words:
            trie.insert(word)
        n = len(board)
        m = len(board[0])
        self.vis = [[False for i in range(m)] for x in range(n)]
        self.ans = []
        for i in range(n):
            for j in range(m):
                self.dfs(board, i, j, [], trie)
        return list(set(self.ans))


    def dfs(self, board, sx, sy, st, trie):
        if sx < 0 or sx >= len(board) or sy < 0 or sy >= len(board[0]):
            return
        if self.vis[sx][sy]:
            return
        if board[sx][sy] not in trie.children:
            return
        trie = trie.children[board[sx][sy]]

        st.append(board[sx][sy])

        if trie.isEnd:
            self.ans.append(''.join(st))

        self.vis[sx][sy] = True
        self.dfs(board, sx + 1, sy, st, trie) 
        self.dfs(board, sx - 1, sy, st, trie) 
        self.dfs(board, sx, sy + 1, st, trie) 
        self.dfs(board, sx, sy - 1, st, trie) 
        self.vis[sx][sy] = False
        st.pop()