leetcode : word search

Word Search - LeetCode

Word Search - LeetCode

 

2차원 행렬에 알파벳이 들어가있고 문자열word가 하나 주어진다.

이 행렬에서 인접한 알파벳을 따라가서 문자열 word를 만들 수 있는지 검사하는 문제다.

간단하게 dfs로 구현했다.

 

class Solution:
    def search(self, board, x, y, word):
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
        
        if len(word) == 1 and board[x][y] == word:
            return True
        
        result = False
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx >= 0 and nx < len(board) and ny >= 0 and ny < len(board[0]) and board[nx][ny] == word[1]:
                tmp = board[x][y]
                board[x][y] = "$"
                result = result or self.search(board, nx, ny, word[1:])
                board[x][y] = tmp
                
        
        return result
    
    def exist(self, board: List[List[str]], word: str) -> bool:
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    if self.search(board, i, j, word):
                        return True
                    
        return False

 

다른 사람 풀이도 볼까?

 

def exist(self, board, word):
    if not board:
        return False
    for i in xrange(len(board)):
        for j in xrange(len(board[0])):
            if self.dfs(board, i, j, word):
                return True
    return False

# check whether can find word, start at (i,j) position    
def dfs(self, board, i, j, word):
    if len(word) == 0: # all the characters are checked
        return True
    if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or word[0]!=board[i][j]:
        return False
    tmp = board[i][j]  # first character is found, check the remaining part
    board[i][j] = "#"  # avoid visit agian 
    # check whether can find "word" along one direction
    res = self.dfs(board, i+1, j, word[1:]) or self.dfs(board, i-1, j, word[1:]) \
    or self.dfs(board, i, j+1, word[1:]) or self.dfs(board, i, j-1, word[1:])
    board[i][j] = tmp
    return res

디테일한 부분에서 아주 살짝 다르긴한데 똑같은 알고리즘이다. 굳