题目描述

单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 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) {
    $n = strlen($s);
    $dp = array_fill(0, $n + 1, false); // 初始化动态规划数组
    $dp[0] = true; // 空字符串总是可以被拆分

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

    return $dp[$n];
}

// 示例用法
$s = "leetcode";
$wordDict = ["leet", "code"];
echo wordBreak($s, $wordDict) ? "true" : "false"; // 输出 true

Python 代码示例

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

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

    return dp[n]

# 示例用法
s = "leetcode"
wordDict = ["leet", "code"]
print(wordBreak(s, wordDict))  # 输出 True

JavaScript 代码示例

function wordBreak(s, wordDict) {
    const n = s.length;
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;

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

    return dp[n];
}

// 示例用法
const s = "leetcode";
const wordDict = ["leet", "code"];
console.log(wordBreak(s, wordDict)); // 输出 true

以上代码示例展示了如何使用动态规划算法解决单词拆分问题，通过遍历字符串和字典中的单词，逐步构建出一个能够表示是否可拆分的布尔数组 dp。在面试中，能够清晰地解释算法思路和展示代码能力是非常重要的。