소프트웨어에 대한 모든 것

LeetCode 풀기 - 79. Word Search 본문

알고리즘/LeetCode

LeetCode 풀기 - 79. Word Search

앤테바 2022. 3. 30. 09:38
반응형

79. Word Search

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

 

Word Search - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

문제)

솔루션1) 백트래킹

class Solution:
    def exist(self, board, word):
        m = len(board)
        n = len(board[0])
        path = set()
        def bt(row, col, idx):
            if idx >= len(word):
                return True
            
            # board boundary check
            if not (0 <= row < m):
                return False
            if not (0 <= col < n):
                return False
            
            if board[row][col] != word[idx]:
                return False
            
            if (row, col) in path:
                return False

            path.add((row, col))
            res = bt(row - 1, col, idx+1) or bt(row + 1, col, idx+1) or bt(row, col - 1, idx+1) or bt(row, col + 1, idx+1)
            path.remove((row, col))
            return res
    
        for r in range(m):
            for c in range(n):
                if bt(r, c, 0):
                    return True
        return False

 

반응형

'알고리즘 > LeetCode' 카테고리의 다른 글

462. Minimum Moves to Equal Array Elements II  (0) 2022.07.01
5. Longest Palindromic Substring  (0) 2022.05.24
LeetCode 풀기 - 101. Symmetric Tree  (0) 2022.03.26
LeetCode 풀기 - 328. Odd Even Linked List  (0) 2022.03.26
LeetCode 풀기 - 146. LRU Cache  (0) 2022.03.26
'알고리즘/LeetCode' Related Articles more
Comments