Dado un tablero 2D y una palabra, busque si la palabra existe en la cuadrícula.
La palabra se puede construir a partir de letras de una celda adyacente secuencialmente, donde las celdas «adyacentes» son las vecinas horizontal o verticalmente. La misma celda de letra no se puede utilizar más de una vez.
Por ejemplo, tablero dado =
[ ["ABCE"], ["SFCS"], ["ADEE"] ]
palabra = «ABCCED», -> devuelve verdadero,
palabra = «VER», -> devuelve verdadero,
palabra = «ABCB», -> devuelve falso.
Solución Java
Este problema se puede resolver utilizando un algoritmo DFS típico.
public boolean exist(char[][] board, String word) { int m = board.length; int n = board[0].length; boolean result = false; for(int i=0; i<m; i++){ for(int j=0; j<n; j++){ if(dfs(board,word,i,j,0)){ result = true; } } } return result; } public boolean dfs(char[][] board, String word, int i, int j, int k){ int m = board.length; int n = board[0].length; if(i<0 || j<0 || i>=m || j>=n){ return false; } if(board[i][j] == word.charAt(k)){ char temp = board[i][j]; board[i][j]='#'; if(k==word.length()-1){ return true; }else if(dfs(board, word, i-1, j, k+1) ||dfs(board, word, i+1, j, k+1) ||dfs(board, word, i, j-1, k+1) ||dfs(board, word, i, j+1, k+1)){ return true; } board[i][j]=temp; } return false; } |
Del mismo modo, a continuación se muestra otra forma de escribir este algoritmo.
public boolean exist(char[][] board, String word) { for(int i=0; i<board.length; i++){ for(int j=0; j<board[0].length; j++){ if(dfs(board, word, i, j, 0)){ return true; } } } return false; } public boolean dfs(char[][] board, String word, int i, int j, int k){ if(board[i][j]!=word.charAt(k)){ return false; } if(k>=word.length()-1){ return true; } int[] di={-1,0,1,0}; int[] dj={0,1,0,-1}; char t = board[i][j]; board[i][j]='#'; for(int m=0; m<4; m++){ int pi=i+di[m]; int pj=j+dj[m]; if(pi>=0&&pi<board.length&&pj>=0&&pj<board[0].length&&board[pi][pj]==word.charAt(k+1)){ if(dfs(board,word,pi,pj,k+1)){ return true; } } } board[i][j]=t; return false; } |
