[LeetCode][Python3] 79. Word Search

Problem :

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

My Solution :

class Solution:

def exist(self, board, word: str) -> bool:

R, C = len(board), len(board[0])

def dfs(row, col, word):

if not word:

return True

origin = board[row][col]

board[row][col] = '#'

for r, c in (

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

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

if (0 <= r < R and 0 <= c < C and

board[r][c] == word[0] and dfs(r, c, word[1:])):

return True

board[row][col] = origin

for row in range(R):

for col in range(C):

if (board[row][col] == word[0] and

dfs(row, col, word[1:])):

return True

return False

Comment :

전형적인 백트래킹 (DFS) 문제이다. 고민 없이 바로 일반적인 패턴을 적용했고 쉽게 통과했다. 확실히 문제를 많이 풀어보니 유형에 익숙해지고 자신감이 생긴다.