[抄题]:
给出一个字符串s和一个词典,判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。
s = "lintcode"
dict = ["lint","code"]
返回 true 因为"lintcode"可以被空格切分成"lint code"
[思维问题]:
看到字符串就怕:还是要掌握一般规律
[一句话思路]:
还是看rU手册456页的解法吧
前部完美切分+后部是单词
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
"aaaaaaa" ["aaaa","aa"] false。f[2] = f["li"] f[0] f[全部]都是true
lin完美切分+t在词典中
[一刷]:
- 布尔型can数组的长度是字符串长度+1,不是词典数+1
[二刷]:
- i <= s.length() 表示最后一位边界也要处理
- 取子串的方法是.substring()
[三刷]:
[四刷]:
[五刷]:
[五分钟肉眼debug的结果]:
[总结]:
为了取出长度为j的单词,起点其实是i - j
[复杂度]:Time complexity: O(n*l^2+m) Space complexity: O(n^2)
查询字符串是否在词典中也是n
N字符串长度
M单词个数
L单词平均长度
[英文数据结构或算法,为什么不用别的数据结构或算法]:
从右边开始切割,待判断单词由短到长,割到最大单词长度L还没有即可终止。
从左边开始切割,待判断单词由长到短,复杂度太高。
hash map查询单词,长度L不可忽略时,复杂度是L, 可忽略时为1
[其他解法]:
[Follow Up]:
[LC给出的题目变变变]:
word break2
[代码风格] :
public class Solution {
/*
* @param s: A string
* @param dict: A dictionary of words dict
* @return: A boolean
*/
//maxLength
private int maxLength (Set<String> dict) {
int max = 0;
for (String word : dict) {
max = Math.max(max, word.length());
}
return max;
}
public boolean wordBreak(String s, Set<String> dict) {
//corner case
if (s == null || dict == null) {
return false;
}
//state
//boolean can[] = new boolean[dict.size() + 1];
boolean can[] = new boolean[s.length() + 1];
int max_len = maxLength (dict);
//initialization
can[0] = true;
//function
for (int i = 1; i <= s.length(); i++) {
can[i] = false;
for (int j = 0; j <= i && j <= max_len; j++) {
if (can[i - j] == false) {
continue;
} String word = s.substring(i - j, i);
if (dict.contains(word)) {
can[i] = true;
break;
}
}
}
//answer
return can[s.length()];
}
}