题目描述

单词拆分：给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分成一个或多个在字典中出现的单词。

说明：

• 你可以假设字典中没有重复的单词。
• 你可以假设 s 中的所有单词都由小写字母组成。

示例 1:

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: s 可以被拆分成 "leet code"。

示例 2:

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: s 可以被拆分成 "apple pen apple"。
   注意你可以重复使用字典中的单词。

示例 3:

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

PHP 代码示例

function wordBreak($s, $wordDict) {
    $wordSet = array_flip($wordDict); // 将单词列表转换为哈希集合以提高查找效率
    $n = strlen($s);
    $dp = array_fill(0, $n + 1, false); // dp[i] 表示 s 的前 i 个字符是否能被拆分成单词
    $dp[0] = true; // 空字符串总是可以被拆分

    for ($i = 1; $i <= $n; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if ($dp[$j] && isset($wordSet[substr($s, $j, $i - $j)])) {
                $dp[$i] = true;
                break;
            }
        }
    }

    return $dp[$n];
}

Python 代码示例

def wordBreak(s, wordDict):
    wordSet = set(wordDict)  # 将单词列表转换为集合以提高查找效率
    n = len(s)
    dp = [False] * (n + 1)  # dp[i] 表示 s 的前 i 个字符是否能被拆分成单词
    dp[0] = True  # 空字符串总是可以被拆分

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

    return dp[n]

JavaScript 代码示例

function wordBreak(s, wordDict) {
    const wordSet = new Set(wordDict); // 将单词列表转换为集合以提高查找效率
    const n = s.length;
    const dp = new Array(n + 1).fill(false); // dp[i] 表示 s 的前 i 个字符是否能被拆分成单词
    dp[0] = true; // 空字符串总是可以被拆分

    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && wordSet.has(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[n];
}

码小课：以上代码示例展示了如何使用动态规划（Dynamic Programming, DP）解决单词拆分问题。在码小课网站上，你可以找到更多关于算法和数据结构的详细解析和练习，帮助你进一步提升编程能力。