[LeetCode每日一题]139. Word Break
2020/3/8小于 1 分钟
题目如下:
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Example:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
139. Word Break 给定一个字符串s和一个字典wordDict,判断s是否可以由字典中的词组成。 这道题可以用动态规划解决,设dp[i]表示长度为i的字符是否满足条件,求解该值需要进行一层循环,变量j从1递增到max(i,最长单词的长度),dp[i]为真的条件是dp[j]==true&&s.subString(i-j,j)在字典中。 实现代码如下:
class Solution {
public boolean wordBreak(String s, List wordDict) {
int len = s.length();
boolean[] dp = new boolean[len + 1];
int maxLen = 0;
for (String word : wordDict) {
maxLen = Math.max(maxLen, word.length());
}
dp[0] = true;
Set dict = new HashSet<>();
dict.addAll(wordDict);
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= i && j <= maxLen; j++) {
if (dp[i - j] && dict.contains(s.substring(i-j, i))) {
dp[i] = true;
break;
}
}
}
return dp[len];
}
}