方法1—回溯

很简单的回溯题

给出两种实现方式，思路完全一样的。

c++代码

  1. class Solution {
  2. public:
  3.     int flag;
  4.     vector<vector<char>> vocab;
  5.     vector<vector<int>> vv;
  7.     void dfs(int i, int j, int bottom, int right, string word, int idx){
  8.         if(idx == word.size()){
  9.             flag = 1;
  10.             return;
  11.         }
  12.         if(i < 0 || i > bottom || j < 0 || j > right)    return;
  13.         if(flag==1) return;
  14.         if(j < right && vv[i][j+1] == 0 && vocab[i][j+1] == word[idx]){
  15.             vv[i][j+1] = 1;
  16.             dfs(i, j+1, bottom, right, word, idx+1);
  17.             vv[i][j+1] = 0;
  18.         }
  19.         if(flag==1) return;
  20.         if(j > 0 && vv[i][j-1] == 0 && vocab[i][j-1] == word[idx]){
  21.             vv[i][j-1] = 1;
  22.             dfs(i, j-1, bottom, right, word, idx+1);
  23.             vv[i][j-1] = 0;
  24.         }
  25.         if(flag==1) return;
  26.         if(i > 0 && vv[i-1][j] == 0 && vocab[i-1][j] == word[idx]){
  27.             vv[i-1][j] = 1;
  28.             dfs(i-1, j, bottom, right, word, idx+1);
  29.             vv[i-1][j] = 0;
  30.         }
  31.         if(flag==1) return;
  32.         if(i < bottom && vv[i+1][j] == 0 && vocab[i+1][j] == word[idx]){
  33.             vv[i+1][j] = 1;
  34.             dfs(i+1, j, bottom, right, word, idx+1);
  35.             vv[i+1][j] = 0;
  36.         }
  37.     }
  39.     bool exist(vector<vector<char>>& board, string word) {
  40.         vocab = board;
  41.         flag = 0;
  42.         int raw = board.size(), column = board[0].size();
  43.         vector<int> v(column, 0);
  44.         for(int i=0; i<raw; i++)   vv.push_back(v);
  46.         for(int i=0; i<raw; i++){
  47.             for(int j=0; j<column; j++){
  48.                 if(board[i][j] == word[0]){
  49.                     vv[i][j] = 1;
  50.                     // 当前元素的行、列，board的下边界、右边界，单词及索引
  51.                     dfs(i, j, raw-1, column-1, word, 1); 
  52.                     vv[i][j] = 0;
  53.                 }
  54.                 if(flag)    return true;
  55.             }
  56.         }
  57.         return false;
  59.     }
  60. };

java代码

class Solution {
    private boolean[][] marked;
    private int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int raw, column;   //board的行,列
    private char[][] board;
    private String word;

    boolean inArea(int i, int j){
        if(i >= 0 && i < raw && j >= 0 && j < column)
            return true;
        return false;
    }

    boolean dfs(int i, int j, int idx){
        if(idx == word.length()-1)
            return board[i][j] == word.charAt(idx);

        if(board[i][j] == word.charAt(idx)){
            marked[i][j] = true;
            for(int k=0; k<4; k++){
                int new_x = i + direction[k][0];
                int new_y = j + direction[k][1];
                if(inArea(new_x, new_y) && !marked[new_x][new_y]){
                    if(dfs(new_x, new_y, idx+1))    return true;
                }
            }
            marked[i][j] = false;
        }
        return false;
    }

    public boolean exist(char[][] board, String word) {
        this.word = word;
        this.board = board;
        raw = board.length;
        column = board[0].length;
        marked = new boolean[raw][column];

        for(int i=0; i<raw; i++){
            for(int j=0; j<column; j++){
                if(dfs(i, j, 0))    return true;
            }
        }
        return false;

    }
}