单词拆分 I · Word Break

时间:2023-03-07 14:06:20

[抄题]:

给出一个字符串s和一个词典,判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。

s = "lintcode"

dict = ["lint","code"]

返回 true 因为"lintcode"可以被空格切分成"lint code"

[思维问题]:

看到字符串就怕:还是要掌握一般规律

[一句话思路]:

还是看rU手册456页的解法吧

前部完美切分+后部是单词

[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):

[画图]:

单词拆分 I · Word Break

"aaaaaaa" ["aaaa","aa"] false。f[2] = f["li"] f[0] f[全部]都是true

lin完美切分+t在词典中

[一刷]:

  1. 布尔型can数组的长度是字符串长度+1,不是词典数+1

[二刷]:

  1. i <= s.length() 表示最后一位边界也要处理
  2. 取子串的方法是.substring()

[三刷]:

[四刷]:

[五刷]:

[五分钟肉眼debug的结果]:

[总结]:

为了取出长度为j的单词,起点其实是i - j

单词拆分 I · Word Break

[复杂度]:Time complexity: O(n*l^2+m) Space complexity: O(n^2)

查询字符串是否在词典中也是n

N字符串长度

M单词个数

L单词平均长度

[英文数据结构或算法,为什么不用别的数据结构或算法]:

从右边开始切割,待判断单词由短到长,割到最大单词长度L还没有即可终止。

从左边开始切割,待判断单词由长到短,复杂度太高。

单词拆分 I · Word Break

hash map查询单词,长度L不可忽略时,复杂度是L, 可忽略时为1

[其他解法]:

[Follow Up]:

[LC给出的题目变变变]:

word break2

[代码风格] :

单词拆分 I · Word Break

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()];
}
}