leetcode hot100【LeetCode 139. 单词拆分】java实现

LeetCode 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

Java 实现代码

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 将词典转换为集合，方便快速查找
        Set<String> wordSet = new HashSet<>(wordDict);
        // 初始化dp数组，dp[i]表示s[0:i]是否可以被拆分
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;  // 空字符串可以被拆分
        // 遍历字符串s的每个位置
        for (int i = 1; i <= s.length(); i++) {
            // 检查从前面的某个位置j到当前位置i的子串是否在wordDict中
            for (int j = 0; j < i; j++) {
                // 如果dp[j]为true，并且s[j:i]在wordDict中，则更新dp[i]
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;  // 找到满足条件的子串后，跳出循环
                }
            }
        }
        // 返回s[0:n]是否可以被拆分
        return dp[s.length()];
    }
}

解题思路

1. 初始化：创建一个布尔数组 dp，长度为 s.length() + 1，其中 dp[i] 表示字符串 s 的前 i 个字符能否被拆分成字典中的单词。初始化 dp[0] 为 true，因为空字符串可以被拆分。

2. 状态转移：遍历字符串 s 的每个位置 i，对于每个位置 i，再遍历之前的每个位置 j，判断 dp[j] 是否为 true，并且 s.substring(j, i) 是否在 wordDict 中。

3. 结果返回：最终返回 dp[s.length()]，表示整个字符串 s 是否可以被拆分。

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是字符串 s 的长度。最坏情况下，我们需要检查所有子串。
• 空间复杂度：O(n)，需要一个大小为 n + 1 的数组 dp 来存储中间结果。