[LeetCode] 79. Word Search

Word Search - LeetCode

입력 & 출력

m x n 크기의 배열에 문자가 들어있다.
문자열이 주어졌을 때 문자들이 연결되어있다면 true를, 아니라면 false를 반환해라.

풀이

이중 포문을 돌려 문자열 첫번째와 같은 문자를 찾아내, 이어지는 문자가 원하는 문자인지 확인한다
양 옆과 위 아래 모두 확인해야한다 i와 j 오버플러우에 주의하자
방문 유무를 카운팅으로 판별하다 끊임없는 오류로 Bool로 바꾸었더니 원활하게 진행된다
흔히 할 수 있는 실수가 if문의 나열인데 [i+1][j] [i][j+1] ...
if문을 나열하면 우선순위가 생기며 자잘한 오류가 생기니 한번에 같이 작성하자

Swift 전체 코드

class Solution {
    func exist(_ board: [[Character]], _ word: String) -> Bool {
    var boards = Array(repeating: Array(repeating: false, count: board[0].count), count: board.count)
    let words = word.map { $0 }
    
    func dfs(board: [[Character]], _ wordContent : [Character], i:Int, j:Int, visited:[[Bool]], index:Int) -> Bool {
        if index == wordContent.count {
            return true
        }
        guard i >= 0 && i < board.count && j >= 0 && j < board[0].count,
              !boards[i][j] && board[i][j] == words[index] else {
            return false
        }
        
        boards[i][j] = true
        
        if dfs(board: board, words, i: i+1, j: j, visited: boards, index: index+1) ||
            dfs(board: board, words, i: i, j: j+1, visited: boards, index: index+1) ||
            dfs(board: board, words, i: i, j: j-1, visited: boards, index: index+1) ||
            dfs(board: board, words, i: i-1, j: j, visited: boards, index: index+1) {
            return true
        }
        boards[i][j] = false
        
        return false
    }
    
    for i in 0..<board.count {
        for j in 0..<board[0].count {
            if board[i][j] == words[0] && dfs(board: board, words, i: i, j: j, visited: boards, index: 0) {
                return true
            }
        }
    }
    
    return false
    }
}