請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來判斷在一個(gè)矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一格開始，每一步可以在矩陣中向左、右、上、下移動(dòng)一格。如果一條路徑經(jīng)過了矩陣的某一格，那么該路徑不能再次進(jìn)入該格子。例如，在下面的3×4的矩陣中包含一條字符串“bfce”的路徑（路徑中的字母用加粗標(biāo)出）。
[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]
但矩陣中不包含字符串“abfb”的路徑，因?yàn)樽址牡谝粋€(gè)字符b占據(jù)了矩陣中的第一行第二個(gè)格子之后，路徑不能再次進(jìn)入這個(gè)格子。

思考： 在矩陣中比對(duì)字符路徑情況下，每次我們選對(duì)了一個(gè)字符，選擇下一個(gè)字符時(shí)都面臨著4中選擇（如果不考慮矩陣邊界的情況，上、左、右、下）。如果選擇了其中一個(gè)選項(xiàng)，進(jìn)入下一步，又面臨新的選項(xiàng)。我們就重復(fù)選擇，直到到達(dá)最終的狀態(tài)。類似這種每一步所有可能選項(xiàng)里系統(tǒng)地選擇一個(gè)可行的解決方案，回溯法非常適合這種多步驟的問題。

實(shí)際上回溯法類似枚舉的搜索嘗試過程，也就是一個(gè)個(gè)去試，我們解這道題也是通過一個(gè)個(gè)去試。

算法:

  func exist(_ board: [[Character]], _ word: String) -> Bool {
        var board = board
        
        let rows = board.count
        let columns = board.first!.count
        
        let words = Array(word)
        // 從[0][0]開始循環(huán)遍歷某個(gè)點(diǎn)開始查找是否存在字符序列
        for i in 0..<rows {
            for j in 0..<columns {
                if hasPathCore(&board, words, i: i, j: j, index: 0) {
                    return true
                }
            }
        }
        return false
    }
    
    func hasPathCore(_ borad: inout [[Character]],_ word: [Character],i: Int, j:Int,index: Int)->Bool {
        // 如果 數(shù)據(jù)越界 或者 未找到對(duì)應(yīng)的字符， index表示查找的是字符串中第幾個(gè)字符
        if i<0 || i >= borad.count || j < 0 || j >= borad.first!.count || borad[i][j] != word[index] {
            return false
        }
      // 如果尋找的字符的下標(biāo)等于字符串的長度-1 說明字符串已經(jīng)匹配完畢。
        if index == word.count-1 {
            return true
        }
      //把當(dāng)前坐標(biāo)的值保存下來，為了在最后復(fù)原
        let temp = borad[i][j]
        borad[i][j] = "."
        //走遞歸，沿著當(dāng)前坐標(biāo)的上下左右4個(gè)方向查找下一個(gè)字符
        let res = hasPathCore(&borad, word, i: i+1, j: j, index: index+1) ||
        hasPathCore(&borad, word, i: i-1, j: j, index: index+1) ||
        hasPathCore(&borad, word, i: i, j: j+1, index: index+1) ||
        hasPathCore(&borad, word, i: i, j: j-1, index: index+1)
       //遞歸之后再把當(dāng)前的坐標(biāo)復(fù)原
        borad[i][j] = temp
        return res
    }