LeetCode 488. Zuma Game

题目链接 Zuma Game



这题击败了百分之百的人,耗时5ms,感觉出结果的时候还是比较惊喜..不过 wa 了几次.

这题就是一个稍微复杂一些的 dfs,题目中的数据范围都不大明显领着你玩 recursive思路是

用一个 for 循环遍历选择一个子串(子串的特点是子串里面每个字符都相同),然后对剩余子串做相同操作,如果传入函数的子串长度为0则视为递归结束条件,直接返回0

talk is cheap, show me the code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public static int findMinStep(String board, String hand) {
int[] a = new int[26];
for (int i = 0; i < hand.length(); i++) {
a[hand.charAt(i) - 'A']++;
}
return dfs(board, a);
}

private static int dfs(String string, int[] c) {
if (string.length() == 0) {
return 0;
}
int result = string.length() * 2 + 1;
for (int i = 0; i < string.length(); ) {
int j = i++;
while (i < string.length() && string.charAt(i) == string.charAt(j)) {
i++;
}
int used = 3 - i + j;
if (used <= c[string.charAt(j) - 'A']) {
if (used > 0) {
c[string.charAt(j) - 'A'] -= used;
}
int sub = dfs(string.substring(0, j) + string.substring(i), c);
if (sub != -1) {
result = Math.min(result, (used <= 0 ? 0 : used) + sub);
}
if (used > 0) {
c[string.charAt(j) - 'A'] += used;
}
}
}
if (result == string.length() * 2 + 1) {
return -1;
}
return result;
}
月月说要给我打赏,就还是放了二维码,😝