作者:
Rushia (みけねこ的鼻屎)
2022-11-24 10:42:5479. 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: