Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

79. Word Search
給你一個二維字元陣列board和一個字串word，在board中搜尋是否存在字元可以串接組成
word。

Example 1:
https://assets.leetcode.com/uploads/2020/11/04/word2.jpg
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word
= "ABCCED"
Output: true

Example 2:
https://assets.leetcode.com/uploads/2020/10/15/word3.jpg
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word
= "ABCB"
Output: false

思路：
1.看起來可以用字典樹或回溯法，但是JAVA要手刻字典樹所以我決定用回溯法搞定。

2.把board的每個點當成起點，如果匹配word長度就+1，如果長度等於word就返回true。

3.走過的格子要標記成已走過，如果下次遇到已走過的格子就跳過。

JavaCode：
-----------------------------------------
class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (backTracking(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean backTracking(char[][] board, String word, int y, int x,
int index) {
        if (index == word.length()) {
            return true;
        }
        if (y < 0 || x < 0 || y == board.length || x == board[0].length) {
            return false;
        }
        if (board[y][x] == '*' || board[y][x] != word.charAt(index)) {
            return false;
        }
        char tmp = board[y][x];
        board[y][x] = '*';
        if (backTracking(board, word, y + 1, x, index + 1)
                || backTracking(board, word, y - 1, x, index + 1)
                || backTracking(board, word, y, x + 1, index + 1)
                || backTracking(board, word, y, x - 1, index + 1)) {
            return true;
        }
        board[y][x] = tmp;
        return false;
    }
}
-----------------------------------------


--
https://i.imgur.com/PIoxddO.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.45.115 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1669257777.A.67E.html
→ PyTorch: 大師
推 twosheep0603: 不知道有沒有辦法加速
推 hahaha021225: 大師
推 NTHUlagka: 大師