返回信息流题目:LeetCode79
题目链接:https://leetcode.com/problems/word-search/description/
题目的大意是:题意为给定二维字符数组，从中是否可以寻找到一条不重复经过同一位置的长链字符能够组成目标字符串。
例子如下：
Given board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
代码提交结果:83 / 87 test cases passed.
Status: Wrong Answer
Submitted: 0 minutes ago
Input:
["ABCE","SFES","ADEE"]
"ABCESEEEFS"
Output:
false
Expected:
true
我对这道题有如下想法：
public class Solution {
public int m, n;
public boolean exist(char[][] board, String word) {
if (board == null) {
return false;
}
if (word == null || word.length() == 0) {
return true;
}
char[] ws = word.toCharArray();
m = board.length;
n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == ws[0]) {
boolean[][] flags = new boolean[m][n];
flags[i][j] = true;
if (backtrack(board, ws, 1, i, j, flags)) {
return true;
}
}
}
}
return false;
}
public boolean backtrack(char[][] board, char[] ws, int index, int x, int y, boolean[][] flags) {
if (index == ws.length) {
return true;
}
if ((x + 1) < m && !flags[x + 1][y]) {
if (board[x + 1][y] == ws[index]) {
boolean[][] new_flags = Arrays.copyOf(flags, m);
new_flags[x + 1][y] = true;
if (backtrack(board, ws, index + 1, x + 1, y, new_flags)) {
return true;
}
}
}
if ((y + 1) < n && !flags[x][y + 1]) {
if (board[x][y + 1] == ws[index]) {
boolean[][] new_flags = Arrays.copyOf(flags, m);
new_flags[x][y + 1] = true;
if (backtrack(board, ws, index + 1, x, y + 1, new_flags)) {
return true;
}
}
}
if (x > 0 && !flags[x - 1][y]) {
if (board[x - 1][y] == ws[index]) {
boolean[][] new_flags = Arrays.copyOf(flags, m);
new_flags[x - 1][y] = true;
if (backtrack(board, ws, index + 1, x - 1, y, new_flags)) {
return true;
}
}
}
if (y > 0 && !flags[x][y - 1]) {
if (board[x][y - 1] == ws[index]) {
boolean[][] new_flags = Arrays.copyOf(flags, m);
new_flags[x][y - 1] = true;
if (backtrack(board, ws, index + 1, x, y - 1, new_flags)) {
return true;
}
}
}
return false;
}
/**
* @param args
*/
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(Arrays.deepToString(Arrays.copyOf(new boolean[2][3], 2)));
System.out.println(Arrays.deepToString(Arrays.copyOf(new boolean[2][3], 2)));
System.out.println(solution.exist(
new char[][] { "ABCE".toCharArray(), "SFES".toCharArray(), "ADEE".toCharArray() }, "ABCESEEEFS"));
}
}
具体代码见附件:
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #94031同步于 2017/9/21
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】关于LeetCode 79 的一点疑问。求问各位大佬，我想知道
sama
2017/9/21镜像同步4 回复
订阅后，新回复会通过你的通知中心匿名送达。
4 条回复
你的boolean[][] new_flags = Arrays.copyOf(flags, m);有问题，复制过来的和原来不一样。试试不用new_flags
flags[x][y - 1] = true;
if (backtrack(board, ws, index + 1, x, y - 1, flags)) {
return true;
}
flags[x][y - 1] = false;
谢谢你，根据你的建议已解决。
【 在 w350053002 的大作中提到: 】
: 你的boolean[][] new_flags = Arrays.copyOf(flags, m);有问题，复制过来的和原来不一样。试试不用new_flags
: flags[x][y - 1] = true;
: if (backtrack(board, ws, index + 1, x, y - 1, flags)) {
: ...................