[LeetCode][Python3] 212. Word Search II

Problem :

https://leetcode.com/problems/word-search-ii/

My Solution :

class Solution:

def findWords(self, board, words):

def make_trie(words):

trie = dict()

for word in words:

curr = trie

for c in word:

curr.setdefault(c, dict())

curr = curr[c]

curr['word'] = word

return trie

def dfs(row, col, trie, res):

c = board[row][col]

if c == '#' or c not in trie:

return

trie = trie[c]

if trie.get('word'):

res.append(trie['word'])

trie['word'] = ''

board[row][col] = '#'

for y, x in (

(row+1, col), (row-1, col),

(row, col+1), (row, col-1)):

if (0 <= y < len(board) and

0 <= x < len(board[0])):

dfs(y, x, trie, res)

board[row][col] = c

trie = make_trie(words)

res = []

for i in range(len(board)):

for j in range(len(board[0])):

dfs(i, j, trie, res)

return res

Comment :

문자열 탐색에는 역시 Trie가 좋다.