[LeetCode][Python3] 212. Word Search II
2019. 4. 24. 00:11 |
프로그래밍/LeetCode
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가 좋다.
'프로그래밍 > LeetCode' 카테고리의 다른 글
| [LeetCode][Python3] 854. K-Similar Strings (0) | 2019.08.15 |
|---|---|
| [LeetCode][Python3] 5. Longest Palindromic Substring (0) | 2019.04.30 |
| [LeetCode][Python3] 140. Word Break II (0) | 2019.04.25 |
| [LeetCode][Python3] 50. Pow(x, n) (0) | 2019.04.24 |
| [LeetCode][Python3] 41. First Missing Positive (0) | 2019.04.23 |
| [LeetCode][Python3] 152. Maximum Product Subarray (0) | 2019.04.22 |
| [LeetCode][Python3] 124. Binary Tree Maximum Path Sum (0) | 2019.04.20 |
| [LeetCode][Python3] 322. Coin Change (0) | 2019.04.20 |
최근에 달린 댓글 최근에 달린 댓글