题目

时间复杂度为O(n^2)，其中n为字符串s的长度。这是因为我们需要遍历字符串s的每个位置，对于每个位置i，又需要从0到i-1的位置进行遍历，因此总的时间复杂度为O(n^2)。

空间复杂度为O(n)，其中n为字符串s的长度。这是因为我们使用了一个大小为n+1的dp数组来保存中间结果，以及一个unordered_set来存储wordDict中的单词。因此，总的空间复杂度为O(n)。

中等

相关标签

给你一个字符串 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 中的所有字符串 互不相同

思路和解题方法

1. 首先，我们将wordDict中的单词存储在一个unordered_set中，这样可以以O(1)的时间复杂度进行单词的查找。
2. 接下来，我们定义一个dp数组，dp[i]表示字符串s的前i个字符能否被拆分成wordDict中的单词。我们初始化dp[0]为true，表示空字符串可以被拆分。
3. 然后，我们从字符串s的第一个字符开始遍历到最后一个字符。对于每个位置i，我们再从0到i-1的位置遍历，记为位置j。我们要判断以位置j为分割点，左边子串能否被拆分，并且右边子串（s[j:i-1]）在wordDict中存在。
4. 具体地，我们检查dp[j]是否为true，即前j个字符能否被拆分成wordDict中的单词。如果dp[j]为true，并且子串s[j:i-1]在wordDict中存在，即wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()，那么我们可以更新dp[i]为true。
5. 在内层循环中，我们不断更新dp[i]的值，直到找到一个满足条件的分割点j，或者遍历完所有可能的分割点。
6. 最终，返回dp[s.size()]，即整个字符串s是否可以被拆分成wordDict中的单词的结果。

复杂度

        时间复杂度:

                O(n^2)

        时间复杂度为O(n^2)，其中n为字符串s的长度。这是因为我们需要遍历字符串s的每个位置，对于每个位置i，又需要从0到i-1的位置进行遍历，因此总的时间复杂度为O(n^2)。

        空间复杂度

                O(n)

        空间复杂度为O(n)，其中n为字符串s的长度。这是因为我们使用了一个大小为n+1的dp数组来保存中间结果，以及一个unordered_set来存储wordDict中的单词。因此，总的空间复杂度为O(n)。

c++ 代码

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {// 将wordDict转化为unordered_set，以便快速查找auto wordDictSet = unordered_set<string>();for (auto word : wordDict) {wordDictSet.insert(word);}// 定义dp数组，dp[i]表示s的前i个字符能否被拆分成wordDict中的单词auto dp = vector<bool>(s.size() + 1);dp[0] = true; // 初始化dp[0]为true，表示空字符串可以被拆分// 遍历字符串s的每个位置，判断从0到当前位置的子串能否被拆分for (int i = 1; i <= s.size(); ++i) {for (int j = 0; j < i; ++j) {// 如果dp[j]为true且s[j:i-1]在wordDict中，则更新dp[i]为trueif (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()) {dp[i] = true;break;}}}// 返回dp[s.size()]，即整个字符串s是否可以被拆分成wordDict中的单词return dp[s.size()];}
};

Java代码

class Solution {public boolean wordBreak(String s, List<String> wordDict) {// 使用HashSet来存储单词，以提高查找速度HashSet<String> set = new HashSet<>(wordDict);// valid数组记录s的前i个字符是否可以被拆分成单词boolean[] valid = new boolean[s.length() + 1];valid[0] = true; // 空字符串可以被拆分for (int i = 1; i <= s.length(); i++) {for (int j = 0; j < i && !valid[i]; j++) {// 如果在j和i之间存在一个分割点，使得前半部分和后半部分都可以被拆分成单词，// 则将valid[i]设为trueif (set.contains(s.substring(j, i)) && valid[j]) {valid[i] = true;}}}return valid[s.length()];}
}

使用了动态规划的思想，通过遍历字符串s的每个位置，判断是否存在一个分割点，使得前半部分和后半部分都可以被拆分成单词。时间复杂度为O(n^2)，空间复杂度为O(n)。

class Solution {public boolean wordBreak(String s, List<String> wordDict) {// dp数组记录s的前i个字符是否可以被拆分成单词boolean[] dp = new boolean[s.length() + 1];dp[0] = true; // 空字符串可以被拆分for (int i = 1; i <= s.length(); i++) {for (String word : wordDict) {int len = word.length();// 如果i的前len个字符可以被拆分成单词，并且最后一个单词和word相等，则将dp[i]设为trueif (i >= len && dp[i - len] && word.equals(s.substring(i - len, i))) {dp[i] = true;break;}}}return dp[s.length()];}
}

使用了动态规划的思想，通过遍历字符串s的每个位置，判断是否存在一个分割点，使得前半部分和后半部分都可以被拆分成单词。时间复杂度为O(n^2)，空间复杂度为O(n)。

class Solution {private Set<String> set;private int[] memo;public boolean wordBreak(String s, List<String> wordDict) {// memo数组用于记录从startIndex开始的子串是否可以被拆分成单词memo = new int[s.length()];// 使用HashSet来存储单词，以提高查找速度set = new HashSet<>(wordDict);return backtracking(s, 0);}public boolean backtracking(String s, int startIndex) {if (startIndex == s.length()) {return true; // 已经遍历到字符串末尾，返回true}if (memo[startIndex] == -1) {return false; // 从startIndex开始的子串已经被标记为不能匹配，直接返回false}for (int i = startIndex; i < s.length(); i++) {String sub = s.substring(startIndex, i + 1);if (!set.contains(sub)) {continue; // 如果拆分出来的单词不在wordDict中，则继续尝试下一个分割点}boolean res = backtracking(s, i + 1);if (res) return true; // 如果后半部分可以被拆分，则返回true}memo[startIndex] = -1; // 从startIndex开始的子串无法匹配，标记为-1return false;}
}

使用了回溯法和记忆化的思想。通过递归地尝试每个分割点，判断前半部分是否可以被拆分成单词，如果可以，则继续递归判断后半部分。为了避免重复计算，使用memo数组记录已经判断过的子串。时间复杂度取决于所有可能的分割方式，最坏情况下为O(2^n)，空间复杂度为O(n)。

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。