力扣139 单词拆分 java实现

139.单词拆分

给你一个字符串s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入:s = "leetcode", wordDict = ["leet", "code"]输出:true解释:返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入:s = "applepenapple", wordDict = ["apple", "pen"]输出:true解释:返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。

示例 3：

输入:s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]输出:false

提示：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s和wordDict[i]仅由小写英文字母组成
• wordDict中的所有字符串互不相同

该题也属于完全背包问题，字典中的物品可以重复使用。dp[n + 1]表示当前位置能否被 字典里的单词组成。每次遍历字典，则只需要判断和当前单词是否相同，或是取出长度为当前单词的长度的单词，判断是否相同，且前面单词是否已经能用词典表示。

public static void main(String[] args) { // 测试用 String s = "leetcode"; List<String> nums = new ArrayList<>(); nums.add("leet"); nums.add( "code"); System.out.println(wordBreak(s, nums)); } public static boolean wordBreak(String s, List<String> wordDict) { int n = s.length(); boolean[] dp = new boolean[n + 1]; for (int i = 0; i <= n; i++) { String target = s.substring(0, i); for (int j = 0; j < wordDict.size(); j++) { String temp = wordDict.get(j); if (temp.equals(target)){ dp[i] = true; break; } int m = temp.length(); if (i >= m){ String target1 = target.substring(i - m, i); if (target1.equals(temp) && dp[i - m]){ dp[i] = true; } } } } System.out.println(Arrays.toString(dp)); return dp[n]; }

以上为记录分享用，代码较差请见谅