Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間3年前 (2022/11/24 10:42)推噓3(3推 0噓 1→)

留言4則, 4人參與討論串117/719 (看更多)

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