算法练习Day46|139.单词拆分
LeetCode:139.单词拆分
139. 单词拆分 - 力扣（LeetCode）
1.思路
字符串是否能被字符串列表中的元素拼接出来，显然是一个背包问题，而且需要排列。
将字典转换为HashSet,利用'.contains()'方法判断是否存在元素与背包中的子串相同，首位置相同则为true，其后位置的判断需要依据当前段是否匹配和前面子串为true的条件！！
2.代码实现
1class Solution {2 public boolean wordBreak(String s, List<String> wordDict) {3 // 将单词字典转换为 HashSet，以便快速查找单词是否存在4 HashSet<String> set = new HashSet<>(wordDict);56 // valid 数组用于记录字符串 s 的前缀是否可以被拆分为字典中的单词7 boolean[] valid = new boolean[s.length() + 1];8 valid[0] = true; // 空字符串可以被拆分9
10 // 遍历字符串 s 的每个位置
11 for (int i = 1; i <= s.length(); i++) {
12 // 遍历当前位置之前的每个位置 j
13 for (int j = 0; j < i && !valid[i]; j++) {
14 // 如果子串 s[j, i] 存在于单词字典中，并且 s[0:j] 可以被拆分，则将 valid[i] 设置为true
15 if (set.contains(s.substring(j, i)) && valid[j]) {
16 valid[i] = true;
17 }
18 }
19 }
20 // 返回 valid 数组的最后一个元素，表示整个字符串 s 是否可以被拆分为字典中的单词
21 return valid[s.length()];
22 }
23}
3.复杂度分析
时间复杂度：O(n^2*m).
空间复杂度：O(m).