LeetCode 79 - Word Search

作者 QIFAN 日期 2017-01-20
LeetCode 79 - Word Search

原题链接: 79. Word Search


题干

给定一个字母的矩阵和一个单词,判断该单词能否由矩阵中相邻的一串字母组成。每个字母在一个单词中只能使用一次。

思路

第一个想法是从开头字母找起, 然后检查周围的四个相邻位置是否能接上。如果一条不同去试下一个,直到所有都试完,如果最后核对到了单词的最后一个字符,返回 true 。因为同一个位置不能用二次,我将访问过的位置标记,如果返回 false ,那再改回来用于下一次。这种方式的时间复杂度是 $O(N^2 * 单词的长度)$ 。

第二个想法,上面的方法会有重复:如果一个位置已经遍历过,就能知道这个位置能够组成的最长单词 b ,下次碰见便只要当前单词 a 加上 b 是否为单词。其实更简单,只要保留那些可以从当前位置到末尾的位置。

第二个想法有很多 Corner case,先按着第一个写。

代码:

public boolean exist(char[][] board, String word) {
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board[0].length; col++) {
if (exist(board, word, row, col, 0)) {
return true;
}
}
}
return false;
}
// row, col 为在矩阵位置,pos 为当前核对到 word 的那个位置
private boolean exist(char[][] board, String word, int row, int col, int pos) {
if (pos == word.length()) {
return true;
}
if (row < 0 || col < 0 || row == board.length || col == board[0].length) {
return false;
}
boolean res = false;
if (word.charAt(pos) == board[row][col]) {
// 标记已访问
board[row][col] = '#';
// 检查相邻,只要有一个找到就算成功
res = exist(board, word, row + 1, col, pos + 1) || exist(board, word, row - 1, col, pos + 1) || exist(board, word, row, col + 1, pos + 1) || exist(board, word, row, col - 1, pos + 1);
// 如果都没有,则重置为原值
if (!res) {
board[row][col] = word.charAt(pos);
}
}
return res;
}