题目描述

求解给定字符串str，是否在字符矩阵array中。要求str中相邻的两个字符，在array中也是相邻字符，并且要求，array中的同一字符，不能使用两次；

我的解法

Beat 66%
回溯法+剪枝
必然要对每一点的每一条路径进行深度遍历，遍历过程中一旦出现：
1.数组越界、2.该点已访问过、3.该点的字符和word对应的index字符不匹配就要对该路径进行剪枝

用了多余空间isvisit[][]

class Solution {
  public boolean dfs(int rowlen,int collen,String str,char [][] board,int [][] isvisit,int now,int i,int j){
  	boolean ok = false;
      if(now >= str.length()) return true;
      isvisit[i][j] = 1;
      if(j + 1 < collen && isvisit[i][j + 1] == 0 && str.charAt(now) == (board[i][j + 1])){
      	ok = dfs(rowlen,collen,str,board,isvisit,now + 1,i,j + 1) || ok;
      	if(ok) return ok;
      }
      if(j - 1 >= 0 && isvisit[i][j - 1] == 0 && str.charAt(now) == (board[i][j - 1]))  {
      	ok = dfs(rowlen,collen,str,board,isvisit,now + 1,i,j - 1) || ok;
      	if(ok) return ok;
      }
      if(i + 1 < rowlen && isvisit[i + 1][j] == 0 && str.charAt(now) == (board[i + 1][j]))  {
      	ok = dfs(rowlen,collen,str,board,isvisit,now + 1,i + 1,j) || ok;
      	if(ok) return ok;
      }
      if(i - 1 >= 0 && isvisit[i - 1][j] == 0 && str.charAt(now) == (board[i - 1][j]))  {
      	ok = dfs(rowlen,collen,str,board,isvisit,now + 1,i - 1,j) || ok;
      	if(ok) return ok;
      }
      isvisit[i][j] = 0;
      return ok;
  }
  public boolean exist(char[][] board, String word) {
  	int lenrow = board.length,lencol = board[0].length;
  	int [][] isvisit = new int[board.length][board[0].length];
  	for(int i = 0;i < lenrow;i++)
          for(int j = 0;j < lencol;j++)
          	isvisit[i][j] = 0;
      for(int i = 0;i < lenrow;i++)
          for(int j = 0;j < lencol;j++)
              if(board[i][j] == word.charAt(0) && dfs(lenrow,lencol,word,board,isvisit,1,i,j))
                  return true;
      return false;
  }
}

简便解法

回溯法
没用多余空间。
由于英文字符范围是0~255，因此遍历某个字符后，进行c^=256操作，该字符在后续匹配中就不会再次匹配到，从而实现标记的效果。在回溯的时候需要将标记的字符还原。

public boolean exist(char[][] board, String word) {
    //巧妙，不用再挨个转换string了
    char[] w = word.toCharArray();
    for (int y=0; y<board.length; y++) {
    	for (int x=0; x<board[y].length; x++) {
    		if (exist(board, y, x, w, 0)) return true;
    	}
    }
    return false;
}

private boolean exist(char[][] board, int y, int x, char[] word, int i) {
	if (i == word.length) return true;
	if (y<0 || x<0 || y == board.length || x == board[y].length) return false;
	if (board[y][x] != word[i]) return false;
	//节约了空间！！！存储了遍历状态，若遍历了，做亦或操作后（用亦或的原因是再做一次亦或能回来），满足不等于word[i]
	board[y][x] ^= 256;
	//可以像我一样拆开，更节约时间
	boolean exist = exist(board, y, x+1, word, i+1)
		|| exist(board, y, x-1, word, i+1)
		|| exist(board, y+1, x, word, i+1)
		|| exist(board, y-1, x, word, i+1);
	//遍历之后要恢复到未访问的状态
	board[y][x] ^= 256;
	return exist;
}