Report: Word Break
O() != TLE. 同样的O(), 但是实际时间还是会导致TLE
题目
思考
first trial: fail
- 这里我还是对DP的状态没搞清楚. 做DP之前, 乃至所有coding之前要想好再动手!
- 对Substring不熟. 对string不熟.
s.substring(a,b+1)表示的是string[a…b]. 所以s.substring(0, s.length()+1)才是返回整个string的. - String的DP表的边界往往是DP[s.length()+1]. 因为
DP[0] = true: 表示: 选择string的0个元素也是符合条件的. 然后结果就是返回DP[s.length()]表示选择s的所有元素. - 这里的optimally equation搞了很久. 其实公式是知道的, 但是一直不对. 其实就是: DP[i] = DP[j], j < i && s.substring(j,i+1)在dict内.
- 代码如下: 第一次写的时候, i,k这样写的话感觉不是很通用. 是在for loop statement的地方写好range, 还是在loop里面+1? 这里因为我的i的范围是1~s.length()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public static boolean wordBreak1st(String s, Set<String> dict) {
if (s == null || s.length() == 0) {
return true;
}
boolean[] F = new boolean[s.length() + 1];
F[0] = true;
for (int i = 1; i < s.length(); ++i) {
for (int k = 0; k < i; ++k) {
if (k == 0) {
if (F[k] == true && dict.contains(s.substring(k, i + 1))) {
// System.out.println(s.substring(k, i + 1) + "," + k + "+" + i);
F[i] = true;
}
} else if (F[k] == true && dict.contains(s.substring(k + 1, i + 1))) {
F[i] = true;
// System.out.println(s.substring(k + 1, i + 1) + "," + k + "+" + i);
break;
}
}
}
// for (boolean b : F)
// System.out.print(b + " ");
return F[s.length() - 1];
}
2nd trial: TLE
- 模仿Code Ganker的写法, 特别是边界的定义. 因为如果是像第一次那样定义的话, k还要分2种情况. 代码很麻烦, 特别是对于index处理越多越容易乱或者出错
- 注意这里的i的范围是一般向的0…s.length()-1. 而j的范围是0…i. 注意这个i是包括的. 因为s.substring(k, i+1). 所以k最大应该取到i, 这样substring就是s[i].
- 这时候的时间复杂度是O(n^2). 不过如同SOF link: substring()是O(n)操作. 所以其实是: O(n^3)的时间复杂度.
- 就算这样, 还是TLE!
- 代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public static boolean wordBreak2nd(String s, Set<String> dict) {
if (s == null || s.length() == 0) {
return true;
}
boolean[] F = new boolean[s.length() + 1]; // string DP always leave 0th as no select always
// true, so the DP space is len+1.
F[0] = true;
for (int i = 0; i < s.length(); ++i) { // notice the init and end of i for states
for (int k = 0; k <= i; ++k) {
if (F[k] == true && dict.contains(s.substring(k, i+1))) {
F[i+1] = true;
}
}
}
return F[s.length()];
}
4th trial: AC
- 看了九章的参考答案. 发现这时候没有的变成O(n). 那只有prune了. 注意到, F[k]==true的时候, 其实并不用判断所有substring(k, i+1). 因为如果这个substring长于dict内单词的长度就可以不用考虑了. 而且通常来说: word的长度最多25左右. 即i-k+1<=maxlen, 即
k>=i-1-maxlen.(注意这里的是i, 不是i+1) 所以可以缩小一点k的取值范围. - 代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public static boolean wordBreak2nd(String s, Set<String> dict) {
if (s == null || s.length() == 0) {
return true;
}
boolean[] F = new boolean[s.length() + 1]; // string DP always leave 0th as no select always
// true, so the DP space is len+1.
F[0] = true;
for (int i = 0; i < s.length(); ++i) { // notice the init and end of i for states
for (int k = 0; k <= i; ++k) {
if (F[k] == true && dict.contains(s.substring(k, i+1))) {
// System.out.println(s.substring(k, i) + "," + k + "+" + i);
F[i+1] = true;
}
}
}
// for (boolean b : F)
// System.out.print(b + " ");
return F[s.length()];
}
总结
- DP问题一定要想清楚state和optimally equation在写代码.
- loop的范围, 以及得到state的方式一定要设计好. 例如这里的是F[i+1]还是F[i]就很大差别. 因为这里要表示的是: 取string前i个元素是成立的. 所以substring(k, i+1), 然后F[i+1]. 这样就是i个元素的state成立, 于是接下来就可以F[k] && substring. 因为这样substring的下确界k正好是kth元素. eg: F[4] && substring(4,7).
1
2
3
4
5l i n t c o d e
0 1 2 3 4 5 6 7
F[4] = true, substring(4, 7+1) => F[7+1] = true. 对于lintcode的例子.
F[7] = true, substring(7, 7+1) => F[7+1] = true. 对于ProgramCreek的例子.