LeetCode No.139.单词拆分
No139.单词拆分
2020.6 .25
题目详情
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明:
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1:
1 2 3
| 输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
|
示例 2:
1 2 3 4
| 输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。 注意你可以重复使用字典中的单词。
|
示例 3:
1 2
| 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
|
题解
常规方法,使用动态规划。我们需要维护动态规划需要的dp数组,dp数组在这题中的意思就是从0到这个位置的字符串是否可以被wordDict拆分。
首先我们需要用变量i遍历这个字符串,在遍历的过程中,截取0-i区域的字符串,并拿它和wordDict进行比较,匹配了就更新dp,没有就更新回溯的遍历point往回寻找dp值为1的位置(也就是上一个可以被拆分的地方)。然后如果可以找到某个point的dp为1,且从point-i组成的字符串可以与wordDict匹配,就更新dp[i]为1(0-point可以被拆分,point-i也找到了匹配,那不就是0-i可以被拆分嘛)。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| import java.util.Arrays; import java.util.List;
public class No139 { public static boolean wordBreak(String s, List<String> wordDict) { int stringsize = s.length(); int[] dp = new int[stringsize + 1]; for (int i = 1; i <= stringsize; i++) { int point = 0; String subs = s.substring(0, i); dp[i] = 0; for (String word : wordDict) { if (subs.equals(word)) { dp[i] = 1; break; } } if (dp[i] == 0) { point = i - 1; } while (point >= 0) { if (dp[point] == 1) { subs = s.substring(point, i); dp[i] = 0; for (String word : wordDict) { if (subs.equals(word)) { dp[i] = 1; break; } } if (dp[i] == 1) { break; } } point--; } } return dp[stringsize] == 1; }
public static void main(String[] args) { String s = "leetcode"; List<String> wordDict = Arrays.asList("leet", "code"); boolean x = wordBreak(s, wordDict); System.out.print(x);
} }
|
提交结果如下

官方代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| public class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> wordDictSet = new HashSet(wordDict); boolean[] dp = new boolean[s.length() + 1]; dp[0] = true; for (int i = 1; i <= s.length(); i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordDictSet.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[s.length()]; } }
作者:LeetCode-Solution 链接:https: 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
|
本以为官方题解应该是执行时间少,内存使用少。然而….
