Swift solution - Backtracking


  • 0
    class Solution {
        func exist(_ board: [[Character]], _ word: String) -> Bool {
            if board.count == 0 {
                return false
            }
            
            let n = board.count
            let m = board[0].count
            let chars = Array(word.characters)
            var visited = [[Bool]](repeatElement([Bool](repeatElement(false, count: m)), count: n))
            
            for i in 0..<n {
                for j in 0..<m {
                    if board[i][j] == chars[0] &&
                        backtracking(board, chars, i, j, 0, &visited)
                        {
                        return true
                    }
                }
            }
            
            return false
        }
        
        func backtracking(_ board: [[Character]], _ chars: [Character], _ i: Int, _ j: Int, _ index: Int, _ visited: inout [[Bool]]) -> Bool {
            if index == chars.count {
                return true
            }
            
            let n = board.count
            let m = board[0].count
            
            if i < 0 || i >= n || j < 0 || j >= m || board[i][j] != chars[index] || visited[i][j] {
                return false
            }
            
            visited[i][j] = true
            if backtracking(board, chars, i - 1, j,     index + 1, &visited) ||
               backtracking(board, chars, i + 1, j,     index + 1, &visited) ||
               backtracking(board, chars, i,     j - 1, index + 1, &visited) ||
               backtracking(board, chars, i,     j + 1, index + 1, &visited) {
                return true
            }
            visited[i][j] = false
            
            return false
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.