반응형
Top 100 Liked Questions 중 하나인 Word Search 풀이를 공유한다.
문제를 읽어보면 dfs로 풀어야 할 것 같은 느낌이 빡 오는 문제이다.
내 풀이
나는 board의 (0, 0)부터 (m-1, n-1)까지 하나씩 돌며 dfs를 사용했다.
그 과정에서 visited라는 board와 같은 크기의 boolean 값으로 이루어진 2차원 리스트를 두었다.
여차 저차 해서 구현한 나의 풀이는 아래와 같으며, 결과는~~
class Solution:
def dfs(self, board, word, row_idx, col_idx, curr_string, visited):
if len(curr_string) == len(word):
if curr_string == word:
return True
return False
if curr_string != word[:len(curr_string)]:
return False
for cal_row, cal_col in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
next_row, next_col = row_idx + cal_row, col_idx + cal_col
if next_row < 0 or len(board) <= next_row or next_col < 0 or len(board[0]) <= next_col:
continue
if visited[next_row][next_col]:
continue
visited[next_row][next_col] = True
if self.dfs(board, word, next_row, next_col,
curr_string + board[next_row][next_col], visited):
return True
visited[next_row][next_col] = False
return False
def exist(self, board: List[List[str]], word: str) -> bool:
for row_idx in range(len(board)):
for col_idx in range(len(board[0])):
if board[row_idx][col_idx] != word[0]:
continue
visited = [[False for _ in range(len(board[0]))] for _ in range(len(board))]
visited[row_idx][col_idx] = True
if self.dfs(board, word, row_idx, col_idx, board[row_idx][col_idx], visited):
return True
return False
정신 나간 성능을 보여주고 있다.
가장 빠른 풀이
가난한 사회 초년생은 Solution을 돈 주고 보기 싫기 때문에 늘 하던 대로 Discuss를 열심히 뒤졌다.
그 결과, 여기에서 다음과 같은 코드로 좋은 결과를 얻을 수 있었다!
class Solution:
def dfs(self, i, word, board, row, col):
if i==len(word):
return True
temp=board[row][col]
board[row][col]='' # to prevent from visiting already visited letter
#here checking for the condition for grid to be on the board as well as if the letter in any of the four direction is the next letter in the word
if 0<=row<len(board) and 0<=col+1<len(board[0]) and board[row][col+1]==word[i]:
#going right
if self.dfs(i+1, word, board, row, col+1):
return True
if 0<=row+1<len(board) and 0<=col<len(board[0]) and board[row+1][col]==word[i]:
#going down
if self.dfs(i+1, word, board, row+1, col):
return True
if 0<=row-1<len(board) and 0<=col<len(board[0]) and board[row-1][col]==word[i]:
#going up
if self.dfs(i+1, word, board, row-1, col):
return True
if 0<=row<len(board) and 0<=col-1<len(board[0]) and board[row][col-1]==word[i]:
#going left
if self.dfs(i+1, word, board, row, col-1):
return True
board[row][col]=temp #restoring the letter for next search
return False
def exist(self, board: List[List[str]], word: str) -> bool:
for row in range(len(board)): #travesing through board
for col in range(len(board[0])):
if board[row][col]==word[0]:
i=0
if self.dfs(i+1, word, board, row, col): #if word found
return True
return False
코드에 필요없는 부분이 있는데, exist 함수에서 i=0은 없애고 i+1 대신 1을 넣으면 된다.
그리고 dfs 함수에서 네 개의 if 문을 아래와 같이 for 문으로 묶어봤는데 이러면 실행 시간이 30ms 정도 증가한다;
아무래도 이런 경우는 for 문보다는 펼쳐서 작성하는 게 조금이라도 더 빨리 되나 보다.
학교에서 이런 경우를 배운 것 같은데.. Unrolling for loop 인가..
for row_cal, col_cal in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
next_row, next_col = row + row_cal, col + col_cal
if (0 <= next_row < len(board) and
0 <= next_col < len(board[0]) and
board[next_row][next_col] == word[i]):
if self.dfs(i+1, word, board, next_row, next_col):
return True
여하튼 내 코드와 다른 점이 몇 가지 있는데,
먼저 나는 visited와 curr_string이라는 쓸모없는 변수를 더 썼다는 점이다.
그래서 공간 효율성을 더 나쁘게 만들기도 했고 그만큼 확인해야 할 것이 많아져 시간 효율성도 낮아졌다.
끝!
반응형
