[JS]回溯算法之矩阵中的路径

题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左右上下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。

思路： 第n个字符满足在字符串的第i个位置相等，如果第n个字符的上下左右也就是n+1路径上没有符合与i+1的字符串的字符相等的话，就倒退到n-1位置重新匹配。

代码实现：

function hasPath(arr, rows, cols, str) {
    if (rows <= 0 || cols <= 0 || !str) return false;
    let strLength = 0;//当前要匹配的字符串下标
    var visitedArr = new Array();
    //初始化标记数组
    for (let i = 0; i < rows; i++) {
        visitedArr[i] = new Array();
        for (let j = 0; j < cols; j++) {
            visitedArr[i][j] = false;
        }
    }
    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            if (hasPathCore(arr, rows, cols, str, strLength, row, col, visitedArr))
                return true;
        }
    }
    return false;
}

function hasPathCore(arr, rows, cols, str, strLength, row, col, visitedArr) {
    if (str[strLength] == undefined) return true;

    var hasPath = false;
    if (row >= 0 && row < rows && col >= 0 && col < cols && arr[row][col] == str[strLength] && !visitedArr[row][col]) {
        visitedArr[row][col] = true;
        ++strLength;
        hasPath = hasPathCore(arr, rows, cols, str, strLength, row, col + 1, visitedArr) ||
            hasPathCore(arr, rows, cols, str, strLength, row, col - 1, visitedArr) ||
            hasPathCore(arr, rows, cols, str, strLength, row + 1, col, visitedArr) ||
            hasPathCore(arr, rows, cols, str, strLength, row - 1, col, visitedArr)

        if (!hasPath) {
            --strLength;
            visitedArr[row][col] = false;
        }
    }
    return hasPath;

}

测试case：

var arr_ = new Array();
var stack = ['a','v','x','s','a','w','s','d','a'];
for(let i=0;i<3;i++){
    arr_[i] = new Array();
    for(let j=0;j<3;j++){
        arr_[i][j] = stack.shift();
    }
}
arr_
(3) [Array(3), Array(3), Array(3)]0: (3) ["a", "v", "x"]1: (3) ["s", "a", "w"]2: (3) ["s", "d", "a"]length: 3__proto__: Array(0)
hasPath(arr_, 3, 3, 'aa')
false
hasPath(arr_, 3, 3, 'asad')
true

git仓库会更新剑指offer的相关数据结构与算法的JS实现版本，频率一周3~5篇左右
git地址