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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/word-break 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解 :

• 本题使用动态规划
  • 动态规划三步走
    1. 定义 dp[i] 含义
       • dp[i] 表示 以下标 i 结尾的字符串，是否包含在字典内
    2. 定义初始值
       • dp[0] = true.
    3. 状态转移方程
       • 双层for循环， 在递推 dp[i] 时, 查看 [0, i - 1] 范围内的字符串
       • 如果 [0, i - 1] 范围内，有某一位置 dp[n] 为 true，并且 字典中包含 字符串[n, 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

// 动态规划
// s = "leetcode", wordDict = ["leet", "code"]
// "leetcode", wordDict = ["leet", "code"]
public boolean wordBreak(String s, List<String> wordDict) {

    // dp[i]表示， 以 i 结尾的子串是否被包含在字典中
    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++) {
            // 以 j 拆分字符串
            // dp[j] == true
            // 且 字符串字典 包含 s.substring(j, i)
            if (dp[j] && wordDict.contains(s.substring(j, i))){
                dp[i] = true;
                break;
            }
        }
    }

    return dp[s.length()];
}

复杂度分析 :

时间复杂度 : O(N ^ 2)

空间复杂度 : O(N)