package LeetCode;

public class LeetCode79 {

// https://leetcode-cn.com/problems/word-search/description/

/// 回溯法

/// 时间复杂度: O(m*n*m*n)

/// 空间复杂度: O(m*n)

// 左，上，右，下移动

private int d[][] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

private int m, n;

private boolean[][] visited;

public boolean exist(char[][] board, String word) {

if (board == null || word == null)

throw new IllegalArgumentException("board or word can not be null!");

m = board.length;

if (m == 0)

throw new IllegalArgumentException("board can not be empty.");

n = board[0].length;

if (n == 0)

throw new IllegalArgumentException("board can not be empty.");

visited = new boolean[m][n];

for (int i = 0; i < m; i++)

for (int j = 0; j < n; j++)

if (searchWord(board, word, 0, i, j))

return true;

return false;

}

// 判断坐标是否在区域内

private boolean inArea(int x, int y) {

return x >= 0 && x < m && y >= 0 && y < n;

}

// 从board[startx][starty]开始, 寻找word[index...word.size())

private boolean searchWord(char[][] board, String word, int index,

int startx, int starty) {

//assert(inArea(startx,starty));

if (index == word.length() - 1)

return board[startx][starty] == word.charAt(index);

if (board[startx][starty] == word.charAt(index)) {

visited[startx][starty] = true;

// 从startx, starty出发,向四个方向寻

for (int i = 0; i < 4; i++) {

int newx = startx + d[i][0];

int newy = starty + d[i][1];

if (inArea(newx, newy) && !visited[newx][newy] &&

searchWord(board, word, index + 1, newx, newy))

return true;

}

visited[startx][starty] = false;

}

return false;

}

public static void main(String args[]) {

char[][] b1 = {{'A', 'B', 'C', 'E'},

{'S', 'F', 'C', 'S'},

{'A', 'D', 'E', 'E'}};

String words[] = {"ABCCED", "SEE", "ABCB"};

for (int i = 0; i < words.length; i++)

if ((new LeetCode79()).exist(b1, words[i]))

System.out.println("found " + words[i]);

else

System.out.println("can not found " + words[i]);

// ---

char[][] b2 = {{'A'}};

if ((new LeetCode79()).exist(b2, "AB"))

System.out.println("found AB");

else

System.out.println("can not found AB");

}

}