数据结构与算法之递归: LeetCode 79. 单词搜索 (Ts 版)

单词搜索

• https://leetcode.cn/problems/word-search/description/

描述

• 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false

• 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用

示例 1

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成
• 进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

Typescript 版算法实现

1 ) 方案1: 回溯

function exist(board: string[][], word: string): boolean {
    const h = board.length, w = board[0].length;
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    const visited = new Array(h);
    for (let i = 0; i < visited.length; ++i) {
        visited[i] = new Array(w).fill(false);
    }
    const check = (i, j, s, k) => {
        if (board[i][j] != s.charAt(k)) {
            return false;
        } else if (k == s.length - 1) {
            return true;
        }
        visited[i][j] = true;
        let result = false;
        for (const [dx, dy] of directions) {
            let newi = i + dx, newj = j + dy;
            if (newi >= 0 && newi < h && newj >= 0 && newj < w) {
                if (!visited[newi][newj]) {
                    const flag = check(newi, newj, s, k + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;
    }

    for (let i = 0; i < h; i++) {
        for (let j = 0; j < w; j++) {
            const flag = check(i, j, word, 0);
            if (flag) {
                return true;
            }
        }
    }
    return false;
};

2 ) 方案2: 回溯优化

function exist(board: string[][], word: string): boolean {
    // 输入的终止条件
    if (board.length === 0) return false
    if (word.length === 0) return true

    //递归函数
    function find(i, j, cur) {
        if (i >= row || i < 0) return false
        if (j >= col || j < 0) return false
        // if()
        let letter = board[i][j]
        // 查询结束判断
        if (letter !== word[cur]) return false
        // 最后一个 也是匹配的
        if (cur == word.length - 1) return true
        board[i][j] = null //选择当前的字母
        // 进行下一步 有一个找到就算
        const ret = find(i + 1, j, cur + 1) ||
            find(i - 1, j, cur + 1) ||
            find(i, j + 1, cur + 1) ||
            find(i, j - 1, cur + 1)
        board[i][j] = letter //回撤
        return ret
    }

    //开始循环找
    const row = board.length
    const col = board[0].length
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            //每一个字母都可以作为起点搜索
            const ret = find(i, j, 0)  //0就是当前查询的字母索引
            if (ret) return ret
        }
    }
    return false //结束的时候还没找到
};

原文地址：https://blog.csdn.net/Tyro_java/article/details/145240191

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！