Leetcode #79: Word Search

func exist(_ board: [[Character]], _ word: String) -> Bool {
    if word.isEmpty {
        return false
    }
    let word = Array(word)
    var board = board
    var candidates = [(Int, Int)]()
    for i in 0..<board.count {
        for j in 0..<board[0].count {
            if board[i][j] == word[0] {
                candidates.append((i,j))
            }
        }
    }
    for candidate in candidates {
        board[candidate.0][candidate.1] = "?"
        if helper(&board, word, candidate.0 + 1, candidate.1, 1) ||
           helper(&board, word, candidate.0 - 1, candidate.1, 1) ||
           helper(&board, word, candidate.0, candidate.1 + 1, 1) ||
           helper(&board, word, candidate.0, candidate.1 - 1, 1) {
           return true
        }
        board[candidate.0][candidate.1] = word[0]
    }
    return false
}

private func helper(_ board: inout [[Character]], _ word: [Character], _ i: Int, _ j: Int, _ index: Int) -> Bool {
    if index == word.count {
        return true
    }
    guard i >= 0 && i < board.count && j >= 0 && j < board[0].count else {
        return false
    }
    if board[i][j] == word[index] {
        board[i][j] = "?"
        if helper(&board, word, i + 1, j, index+1) || helper(&board, word, i - 1, j, index+1) ||
            helper(&board, word, i, j + 1, index+1) || helper(&board, word, i, j - 1, index+1) {
            return true
        }
        board[i][j] = word[index]
        return false
    } else {
        return false
    }
}