讨论/《中级算法》 - 单词搜索/
《中级算法》 - 单词搜索
共 1 个回复

我是不是对剪枝有什么误解啊,怎么效率不咋滴呢。。。

function exist(board: string[][], word: string): boolean {
    const m = board.length;
    const n = board[0].length;
    function backtrack(track: string, row: number, col: number): boolean {
        // console.log(track, row, col);
        if (track === word) {
            return true;
        }
        if (word.indexOf(track) !== 0) {
            return false;
        }
        if (row >= m || row < 0 || col >= n || col < 0 || board[row][col] === "0") {
            return false;
        }
        const newTrack = track + board[row][col], temp = board[row][col];
        board[row][col] = "0";
        const isValid = backtrack(newTrack, row, col + 1)
            || backtrack(newTrack, row + 1, col)
            || backtrack(newTrack, row - 1, col)
            || backtrack(newTrack, row, col - 1);
        board[row][col] = temp;
        return isValid;
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (word.indexOf(board[i][j]) === 0 && backtrack("", i, j)) {
                return true;
            }
        }
    }
    return false;
};