給定一個二維網格?board?和一個字典中的單詞列表 words，找出所有同時在二維網格和字典中出現的單詞。

單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母在一個單詞中不允許被重復使用。

示例:

輸入:?
words = ["oath","pea","eat","rain"] and board =
[
? ['o','a','a','n'],
? ['e','t','a','e'],
? ['i','h','k','r'],
? ['i','f','l','v']
]

輸出:?["eat","oath"]
說明:
你可以假設所有輸入都由小寫字母 a-z?組成。

思路：上一道題改一下，把每一個單詞都判斷一下即可。

class Solution {private boolean[][] marked;// x-1,y// x,y-1 x,y x,y+1// x+1,yprivate int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};// 盤面上有多少行private int m;// 盤面上有多少列private int n;private String word;private char[][] board;//答案數組Set<String> ans=new HashSet<>();//判斷一個字符public List<String> findWords(char[][] board, String[] words) {m = board.length;if (m == 0)return null;n = board[0].length;marked = new boolean[m][n];this.board = board;for(String s:words){for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)marked[i][j]=false;this.word = s;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (dfs(i, j, 0))ans.add(s);}List<String> ansList=new ArrayList<>(ans);Collections.sort(ansList);return ansList;}private boolean dfs(int i, int j, int start) {if (start == word.length() - 1) {return board[i][j] == word.charAt(start);}if (board[i][j] == word.charAt(start)) {marked[i][j] = true;for (int k = 0; k < 4; k++) {int newX = i + direction[k][0];int newY = j + direction[k][1];if (newX >= 0 && newX < m && newY >= 0 && newY < n && !marked[newX][newY]) {if (dfs(newX, newY, start + 1)) {return true;}}}marked[i][j] = false;}return false;} }

?

總結

以上是生活随笔為你收集整理的leetcode212. 单词搜索 II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。