最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

动态规划7–单词拆分

XAMPP相关 admin 47浏览 0评论

来源:LeetCode

难度:中等

描述:     

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明:

  • 拆分时可以重复使用字典中的单词。
  • 你可以假设字典中没有重复的单词。

示例1:

dre0033

示例2:

输入: s = “applepenapple”,wordDict=["apple "," pen"]

输出:true

解释:返回 true因为”applepenapple”可以被拆分成”apple pen app1″。

注意你可以重复使用字典中的单词。

 

示例3:

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

分析:题意还是很明确的,给咱们一个字符串和一个包含单词的数组,让咱们判断字符串全部拆分成数组中的单词,该题要求用空格拆分,那咱们按顺序拆分判断就行,以下是具体解法

解题

方法一:暴力递归法

思路:如分析,咱们按顺序拆分字符串,如果该单词在数组中,那么将剩余的字符串继续拆分,直到字符串为空,即说明能够完全拆分

代码:

 1public boolean wordBreak(String s, List<String> wordDict) {
 2    //当串s为空时,表明全部能够拆分成数组中的元素
 3    if (s == null || s.length() == 0) {
 4        return true;
 5    }
 6    //这里利用set,因为hashSet contains方法为O(1)复杂度,List为O(n) 复杂度
 7    Set<String> strings = new HashSet<>(wordDict);
 8    for (int i = 1; i <= s.length(); i++) {
 9        if (strings.contains(s.substring(0, i))) {
10            //递归剩余的串
11            if (wordBreak(s.substring(i), wordDict)) {
12                return true;
13            }
14        }
15    }
16    return false;
17}

题外话:暴力永远滴神

方法二:动态规划

思路:这里我们申请一个辅助数组dp,长度为n + 1, 每一位用来表示该位置前面的元素能否按照数组中的单词完全拆分,即dp[i] 表示字符串的第 0 ~ i 位能否用数组中的单词完全拆分

  1. 首先 dp[0] = true,因为辅助数组长为n+1,第0位代表空字符串,一定能被切分
  2. 紧接着咱们遍历字符串每一位,假设dp[i] = true,并且 [i ~ j]能组成数组中的单词,那么一定有 dp[j] = true,即 0 ~ i 能被拆分,当i ~ j能被拆分时,那么一定有0 ~ j 可以被拆分

举个例子:

l e e t c o d e
true false false false true false false false true

题外话:不多比比,咱直接上代码吧

代码:

 1public boolean wordBreak(String s, List<String> wordDict) {
 2    if (s == null || s.length() == 0) {
 3        return true;
 4    }
 5    //这里利用set,因为hashSet contains方法为O(1)复杂度,List为O(n) 复杂度
 6    Set<String> strings = new HashSet<>(wordDict);
 7    boolean[] dp = new boolean[s.length() + 1];
 8    dp[0] = true;
 9    //遍历每个位置
10    for (int i = 1; i <= s.length(); i++) {
11        //判断该位置能否被完全拆分
12        for (int j = 0; j <= i; j++) {
13            //0 ~ j 能完全拆分 & j ~ i 完全拆分  那么一定有 0 ~ i 完全拆分
14            if (dp[j] && strings.contains(s.substring(j, i))) {
15                dp[i] = true;
16                break;
17            }
18        }
19    }
20    return dp[s.length()];
21}

时间复杂度:O(n2) 

空间复杂度:O(n)

 

 

以上仅是个人思路解法

输入: s = “applepenapple”,wordDict=["apple "," pen"]输出:true解释:返回 true因为”applepenapple”可以被拆分成”apple pen app1″。注意你可以重复使用字典中的单词。

 

转载请注明:XAMPP中文组官网 » 动态规划7–单词拆分