iis7怎么安装php网站,php网站开发实例 电子书,金华网站建设微信开发,wordpress 标签消失最近参加工作比较忙#xff0c;抽出时间分享一篇题解#xff0c;希望对大伙有帮助#x1f388;#x1f388; 今天分享一道动态规划的题目#xff0c;大家快刷起来吧#x1f9be;#x1f9be; Problem: 139. 单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字…最近参加工作比较忙抽出时间分享一篇题解希望对大伙有帮助 今天分享一道动态规划的题目大家快刷起来吧 Problem: 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 文章目录 思路复杂度Code 思路
定义dp,dp[i]为字符串s[i]是否可以被拼接最开始的时候dp[0]为true因为空字符是可以被拼接的。我们可以发现这样一个关系
dp[i] dp[i-j] check(s[j:i]) 其中j为0到i中的一个值这个式子的意思就是如果当前字符串将去存在的单词依旧可以被组合那么他就是可以被组合的 check是一个检查函数本题中他的意思是该子字符串是否在单词列表中
复杂度
时间复杂度: O ( n 2 ) O(n^2) O(n2)空间复杂度: O ( n ) O(n) O(n)
Code
class Solution {public boolean wordBreak(String s, ListString wordDict) {SetString word new HashSet(wordDict);boolean[] dp new boolean[s.length()1];dp[0] true;for(int i1; i s.length();i){for(int j0;ji;j){if(dp[j] word.contains(s.substring(j,i))) {dp[i] true;break;}}}return dp[s.length()];}
}
