题目描述补充

单词合成问题： 给定一个字符串数组 words（代表一个字典）和一个目标字符串 target，判断 target 是否可以由 words 数组中的字符串通过连接（不改变顺序）的方式得到。注意，每个字符串在 words 中只能使用一次，且必须完全匹配（即不能是子串或超集）。

示例：

• 输入：words = ["apple", "pen", "applepen", "pine", "pineapple"]，target = "pineappleapple"

• 输出：true（因为 "pineapple" 和 "apple" 连接起来就是 "pineappleapple"）

• 输入：words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]，target = "catdogcatsdog"

• 输出：false（因为无法用给定单词数组中的单词按顺序连接成目标字符串）

PHP 示例代码

function wordBreak($words, $target) {
    $wordSet = array_flip($words); // 将单词数组转换为哈希集合，提高查找效率
    $n = strlen($target);
    $dp = array_fill(0, $n + 1, false); // 动态规划数组，dp[i]表示target的前i个字符是否可以被空格拆分成若干个字典中出现的单词
    $dp[0] = true; // 空字符串总是可以被拆分

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

    return $dp[$n];
}

// 示例用法
$words = ["apple", "pen", "applepen", "pine", "pineapple"];
$target = "pineappleapple";
echo wordBreak($words, $target) ? "true" : "false"; // 输出 true

Python 示例代码

def wordBreak(words, target):
    word_set = set(words)  # 将单词列表转换为集合
    n = len(target)
    dp = [False] * (n + 1)  # 动态规划数组
    dp[0] = True  # 空字符串总是可以被拆分

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

    return dp[n]

# 示例用法
words = ["apple", "pen", "applepen", "pine", "pineapple"]
target = "pineappleapple"
print(wordBreak(words, target))  # 输出 True

JavaScript 示例代码

function wordBreak(words, target) {
    const wordSet = new Set(words); // 将单词数组转换为集合
    const n = target.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] && wordSet.has(target.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[n];
}

// 示例用法
const words = ["apple", "pen", "applepen", "pine", "pineapple"];
const target = "pineappleapple";
console.log(wordBreak(words, target)); // 输出 true

码小课网站中有更多关于算法和数据结构的内容分享，包括动态规划、字符串处理、搜索算法等，欢迎大家学习交流。