在字符网格中查找单词

Question

我必须找出一个给定字符串可以从二维字母网格中构建多少次:

要构建单词，我可以从任何地方开始，然后从三个方向中的一个移动到另一个单元格:

a) same row, next column (right)
b) next row, same column (down)
c) next row, next column (diagonal right and down)

的例子:

char[][] grid = {{'a', 'a'}, {'a', 'a'}};
String str = "aa";
output:
5
Explanation:
a) [0,0][0,1]
b) [0,0][1,0]
c) [1,0][1,1]
d) [0,1][1,1]
e) [0,0][1,1]

这是我到目前为止的代码:

class Solution {

public boolean exist(char[][] grid, String str) {
int m=grid.length,n=grid[0].length;
boolean[][] visited=new boolean[m][n];
int result = 0;
for (int i=0;i< m;i++){
for (int j=0;j<n;j++){               
if (dfs(grid,visited,i,j,0,str)){
result++;
}              
}
}
return result;
}
private boolean dfs(char[][] grid, boolean[][] visited, int x, int y, int i, String str){         
int m=grid.length,n=grid[0].length;   
if (i==str.length()) return true;

if(x<0||x>=m||y<0||y>=n) return false;
if(visited[x][y]) return false;
if(grid[x][y]!=str.charAt(i)) return false;
int[][] dirs={{1,0},{0,1},{1,1}};
visited[x][y]=true;
for (int[] dir: dirs){
int x1=x+dir[0], y1=y+dir[1];
if (dfs(grid, visited, x1, y1, i+1, str)){
return true;
}
}
visited[x][y]=false;
return false;                                                                          
}
}

对于我上面提到的示例输入，我能够得到结果为2而不是5。

我该如何解决这个问题?
有没有其他更好的方法?

Answer 1

从0开始，从列开始，从行开始。创建一个方法boolean check(String word, int startRow, int startCol, int dRow, int dCol)，如果找到从startRow开始的单词，它将返回true,startCol在找到每个字母后将列递增dCol，并将行递增dRow。如果被检查的字母不匹配，或者行或列越界，它可以立即返回false。在循环中调用它三次，第一次使用dRow = 0和dCol = 1，然后将它们都设置为1，然后使用dRow = 1和dCol = 0。

dfs不是一个好名字。

这是我的版本，与上面描述的不完全相同。我决定返回一个int而不是一个布尔值，这样我就可以很容易地将结果加到总数中。为了简化示例，我硬编码了一个字母网格。

public class FindWord {
static char [][] grid = {
{'b','a','d'},
{'o','a','k'},
{'d','a','d'}
};
static final int cols = grid[0].length;
static final int rows = grid.length;
public static void main(String[] args) {
countWords("bad");
countWords("dad");
countWords("oak");
countWords("bod");
countWords("bid");
countWords("aaa");
countWords("aa");
countWords("d");
}
private static void countWords(String word) {
int total = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
total += find(word,r,c,0,1) // across
+ find(word,r,c,1,1) // diagonal
+ find(word,r,c,1,0); // down
}
}
System.out.println(total);
}
private static int find(String word, int row, int col, int dRow, int dCol) {
for (char letter :  word.toCharArray()) {
if (row >= rows || col >= cols || grid[row][col] != letter)
return 0;
row += dRow;
col += dCol;
}
return 1;
}
}

你可能会注意到这个例子有一个单字母单词的错误。它对一个字母单词计数3次，因为它考虑的起始位置与横过、对角线和向下相同。这很容易通过只检查"跨"的条件来解决。如果单词长度为1，则不包含其他两个。我将把它留给你来做调整。