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

Solution.swift

// Time: O(MxN*3^L)
// Space: O(L), don't count matrix change
class Solution {
    let dt: [[Int]] = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    
    func exist(_ board: [[Character]], _ word: String) -> Bool {
        var board = board
        let word: [Character] = Array(word)

        var locs: [[Int]] = []
        for y in 0..<board.count {
            for x in 0..<board[0].count {
                if bt(y, x, 0) { return true }
            }
        }
        return false

        func bt(_ y: Int, _ x: Int, _ i: Int) -> Bool {
            if board[y][x] != word[i] { return false }
            if i == word.count-1 { return true }
            let char = board[y][x]
            board[y][x] = " "
            for d in dt {
                let dy = y + d[0]
                let dx = x + d[1]
                if dy < 0 || dy >= board.count || dx < 0 || dx >= board[0].count { continue }
                if bt(dy, dx, i+1) { return true }
            }
            board[y][x] = char
            return false
        }
    }
}