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: