单词拆分

题目要求

你需要编写一个算法来判断给定的字符串 s 是否可以由字符串列表 wordDict 中的单词组合而成。字符串 s 可以由 wordDict 中的一个或多个单词重复拼接而成，但不必须使用列表中的所有单词。

解题思路

这个问题可以通过动态规划（Dynamic Programming, DP）来解决。动态规划是一种在计算机科学中常用的解决优化问题的方法，它将一个问题分解为相互依赖的子问题，并存储这些子问题的解，以避免重复计算。

以下是解决这个问题的步骤：

初始化 DP 数组：创建一个布尔型的 DP 数组 dp，其长度为 s.length() + 1。dp[i] 表示字符串 s 的前 i 个字符能否由 wordDict 中的单词组成。初始化 dp[0] = true，因为空字符串总是可以由字典中的零个单词组成。
填充 DP 数组：遍历字符串 s 的所有可能的子串，对于每个位置 i（从 1 到 s.length()），执行以下操作：
- 遍历 wordDict 中的所有单词，对于每个单词 word，如果 word 可以放在当前位置 i 之前，并且 dp[i - word.length()] 为 true（这意味着 s 的前 i - word.length() 个字符可以由 wordDict 中的单词组成），那么将 dp[i] 设置为 true。
检查结果：最后，检查 dp[s.length()] 的值。如果为 true，则表示字符串 s 可以由 wordDict 中的单词组合而成；如果为 false，则不可以。

这个算法的关键在于理解如何利用 DP 数组来保存中间结果，以及如何通过这些结果来判断整个字符串是否可以由字典中的单词组成。通过这种方式，我们可以避免对于每个子串的重复检查，从而提高算法的效率。

Golang 版本

package main

import "fmt"

func wordBreak(s string, wordDict []string) bool {
    wordDictSet := make(map[string]bool)
    for _, word := range wordDict {
        wordDictSet[word] = true
    }

    dp := make([]bool, len(s)+1)
    dp[0] = true

    for i := 1; i <= len(s); i++ {
        for j := 0; j < i; j++ {
            if dp[j] && wordDictSet[s[j:i]] {
                dp[i] = true
                break
            }
        }
    }

    return dp[len(s)]
}

func main() {
    s := "bestcode"
    wordDict := []string{"best", "code"}
    fmt.Println(wordBreak(s, wordDict)) // Output: true
}

这段代码定义了一个 wordBreak 函数，它接受一个字符串 s 和一个字符串切片 wordDict 作为输入，并返回一个布尔值，表示 s 是否可以由 wordDict 中的单词组成。在 main 函数中，我们调用了 wordBreak 函数，并打印出结果。

C++版本

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

bool wordBreak(std::string s, std::vector<std::string>& wordDict) {
    std::unordered_set<std::string> dict(wordDict.begin(), wordDict.end());
    std::vector<bool> dp(s.size() + 1, false);
    dp[0] = true;

    for (int i = 1; i <= s.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[s.size()];
}

int main() {
    std::string s = "bestcode";
    std::vector<std::string> wordDict = {"best", "code"};
    std::cout << (wordBreak(s, wordDict) ? "true" : "false") << std::endl;
    return 0;
}

这段 C++代码实现了与 Golang 版本相同的功能。它定义了一个 wordBreak 函数，该函数使用动态规划来确定字符串 s 是否可以由 wordDict 中的单词组成。在 main 函数中，我们创建了一个示例字符串和字典，然后调用 wordBreak 函数，并输出结果。

Python 版本

def wordBreak(s, wordDict):
    word_set = set(wordDict)
    dp = [False] * (len(s) + 1)
    dp[0] = True

    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

    return dp[len(s)]

# 测试代码
s = "bestcode"
wordDict = ["best", "code"]
print(wordBreak(s, wordDict))  # 应输出: True

这段 Python 代码实现了前面描述的动态规划算法。wordBreak 函数检查字符串 s 是否可以由 wordDict 中的单词组成。它使用了一个布尔列表 dp 来跟踪字符串的每个子串是否可以由字典中的单词构成。最后，返回 dp[len(s)] 的值，表示整个字符串 s 是否满足条件。在代码的最后，有一个测试示例来验证函数的正确性。

Java 版本

import java.util.List;
import java.util.HashSet;
import java.util.Set;

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        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++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "bestcode";
        List<String> wordDict = List.of("best", "code");
        System.out.println(solution.wordBreak(s, wordDict)); // 应输出: true
    }
}

这段 Java 代码实现了一个 Solution 类，其中包含了 wordBreak 方法，该方法使用动态规划来判断字符串 s 是否可以由 wordDict 中的单词组成。在 main 方法中，我们创建了一个 Solution 实例，并调用 wordBreak 方法，然后打印出结果。这里使用了 List.of 方法来创建单词列表，这是 Java 9 及以上版本提供的便捷方法。如果你使用的是 Java 8 或更低版本，你需要使用 Arrays.asList 或其他方式来创建单词列表。

Rust 版本

use std::collections::HashSet;

fn word_break(s: String, word_dict: Vec<String>) -> bool {
    let word_set: HashSet<String> = word_dict.into_iter().collect();
    let mut dp = vec![false; s.len() + 1];
    dp[0] = true;

    for i in 1..=s.len() {
        for j in 0..i {
            if dp[j] && word_set.contains(&s[j..i]) {
                dp[i] = true;
                break;
            }
        }
    }

    dp[s.len()]
}

fn main() {
    let s = String::from("bestcode")
    let word_dict = vec![String::from("best"), String::from("code")];
    println!("{}", word_break(s, word_dict)); // 应输出: true
}

这段 Rust 代码实现了 word break 问题的解决方案。它定义了一个word_break函数，该函数接受一个字符串s和一个字符串向量word_dict作为输入，并返回一个布尔值，表示s是否可以由word_dict中的单词组成。在main函数中，我们创建了一个示例字符串和字典，然后调用word_break函数，并输出结果。

总结

上述解法采用了动态规划的方法来解决字符串分割问题。核心思想是使用一个布尔数组 dp 来记录字符串 s 的每个子串是否可以由字典 wordDict 中的单词组成。数组的每个位置 i 对应字符串 s 的前 i 个字符。如果 s 的前 i 个字符可以由 wordDict 中的单词组成，那么 dp[i] 就为 true，否则为 false。

算法的步骤如下：

初始化 dp 数组，长度为 s.length() + 1，并将 dp[0] 设置为 true，表示空字符串总是可以由字典中的零个单词组成。
遍历字符串 s，对于每个位置 i，再遍历 wordDict 中的所有单词。如果某个单词 word 可以放在当前位置 i 之前，并且 dp[i - word.length()] 为 true，则将 dp[i] 设置为 true。
最终，dp[s.length()] 的值即为整个字符串 s 是否可以由 wordDict 中的单词组成的答案。

这种方法的优势在于它避免了重复计算，并且能够高效地解决问题。在实际代码实现中，可以根据不同的编程语言特性进行适当的调整，但核心算法逻辑是一致的。

hot-100