注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
本帖最后由 oio14644 于 2015-6-3 03:19 编辑
file:///C:/Users/WEIWAN~1/AppData/Local/Temp/%W@GJ$ACOF(TYDYECOKVDYB.pnghttp://www.lintcode.com/en/problem/word-break/
为什么写成for (int j = 0; j < i ;j++) 就不能通过oj,而写成for (int j = i - 1; j >= 0 ;j--)就可以
看起来是一样的
我刚刚试了leetcode的oj,两个都能通过
是不是lintcode的bug呢?
求指点
public boolean wordBreak(String s, Set<String> dict) {
int len = s.length();
boolean[] dp = new boolean[len + 1];
// Last test case is SICK
// without this validation it wont pass.
int[] count = new int[26];
//这句意思是统计所有在dict中的字符串里面包含的字符
for (String ss : dict) {
for (int i = 0; i < ss.length(); i++) {
count[ss.charAt(i) - 'a']++;
}
}
//就是如果s里面有dict里面没出现的字符直接判断false
for (int i = 0; i < s.length(); i++) {
if (count[s.charAt(i) - 'a'] == 0) {
return false;
}
}
dp[0] = true;
for (int i = 1; i <= len; i++) {
for (int j = i - 1; j >= 0 ;j--) {
//for (int j = 0; j < i ;j++) { //cannot pass online judge
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[ i ][i] = true;
break;
}
}
}
return dp[len];
}
[/i] |