139. 单词拆分 ——【Leetcode每日一题】

朴灿烈づ我的快乐病毒、 2024-03-25 17:43 72阅读 0赞

### 139. 单词拆分 ###

给你一个字符串 `s` 和一个字符串列表 `wordDict` 作为字典。请你判断是否可以利用字典中出现的单词拼接出 `s` 。

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

##### 示例 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 中的所有字符串 互不相同

#### 思路：（动态规划、完全背包） ####

dict 中的单词没有使用次数的限制，此问题属于 0-1背包 的 **完全背包** ，解法和 **0-1背包** 类似：

[0 - 1背包问题（万能统一代码）][0 - 1]

该问题涉及到字典中单词的**使用顺序**，也就是说物品必须**按一定顺序**放入背包中，例如下面的 dict 就不够组成字符串 “leetcode”：

["lee", "tc", "cod"]

求解顺序的完全背包问题时，对 **物品的迭代** 应该 放在最里层，对 **背包的迭代** 放在外层，只有这样才能让物品 **按一定顺序** 放入背包中。

*  定义dp\[i\] : 字符串长度为 i 的话，dp\[i\] 为 true，表示可以拆分为一个或多个在字典中出现的单词。
 *  状态转移方程为：  
     d p \[ i \] = d p \[ i \] ∣ ∣ d p \[ i − w o r d . l e n t h ( ) \] dp\[i\] = dp\[i\]\\ ||\\ dp\[i - word.lenth()\] dp\[i\]=dp\[i\]∣∣dp\[i−word.lenth()\]

#### 代码：(Java) ####

import java.util.ArrayList;
    import java.util.List;
    
    public class WordBreak {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		String s = "leetcode";
    		List<String> wordDict = new ArrayList<>();
    		wordDict.add("leet");
    		wordDict.add("code");
    
    		System.out.println(wordBreak(s, wordDict));
    	}
        public static  boolean wordBreak(String s, List<String> wordDict) {
        
        	
        	int n = s.length();
        	//dp[i] 表示 s 前 i 字符可以匹配
        	boolean[] dp = new boolean[n + 1];
        	dp[0] = true;
        	for(int i = 1; i <= n; i++) {
        
        		for(String word: wordDict) {
        
        			int l = word.length();
        			if(i >= l && word.equals(s.substring(i - l, i))) {
        
        				dp[i] |= dp[i - l];
        			}
        		}
        	}
        	return dp[n];
        }
    }

##### 运行结果： #####

![在这里插入图片描述][a25582cf19c14c4594b2172de64cf809.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ∗ n u m ) O(n \* num) O(n∗num) , n 为 `s`的长度，num 为`wordDict`中字符串的个数。
 *  **空间复杂度**： O ( n ) O(n ) O(n) , n 为 `s`的长度。

**有序完全背包相似题目：**

[377. 组合总和 Ⅳ ][377. _ _]

##### 注：仅供学习参考！ #####

题目来源：[力扣。][Link 1]

[0 - 1]: https://blog.csdn.net/weixin_43412762/article/details/129485663
[a25582cf19c14c4594b2172de64cf809.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a27893f395c6455aa4cada2714e3e16f.png
[377. _ _]: https://blog.csdn.net/weixin_43412762/article/details/129621199?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22129621199%22%2C%22source%22%3A%22weixin_43412762%22%7D
[Link 1]: https://leetcode.cn/problems/word-break/description/