06单词搜索

单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"
输出：true

示例 2：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"
输出：true

示例 3：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"
输出：false

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

Set<Integer> used = new HashSet<>();
int m = -1;
int n = -1;
boolean existFlag = false;


public boolean exist(char[][] board, String word) {
  m = board.length ;
  n = board[0].length;
  for (int i = 0; i < m *n; i++) {
    if(existFlag) return true;
    used.add(i);
    dfs(board, word, 0, i);
    used.remove(i);
  }

  return existFlag;
}

private void dfs(char[][] board, String word, int index, int curPos) {
  if (existFlag) {
    return;
  }


  int m1 = curPos / n;
  int n1 = curPos % n;

  if (word.length() == used.size() && board[m1][n1] == word.charAt(index)) {
    existFlag = true;
    return;
  }

  if (board[m1][n1] == word.charAt(index)) {
    if (m1 > 0 && !used.contains(curPos - n)) {
      used.add(curPos - n);
      dfs(board, word, index + 1, curPos - n);
      used.remove(curPos - n);
    }
    if (m1+1 < m && !used.contains(curPos + n)) {
      used.add(curPos + n);
      dfs(board, word, index + 1, curPos + n);
      used.remove(curPos + n);
    }

    if (n1 > 0 && !used.contains(curPos - 1)) {
      used.add(curPos - 1);
      dfs(board, word, index + 1, curPos - 1);
      used.remove(curPos - 1);
    }

    if (n1+1 < n && !used.contains(curPos + 1)) {
      used.add(curPos + 1);
      dfs(board, word, index + 1, curPos + 1);
      used.remove(curPos + 1);
    }

  }

}