当前位置： 面试刷题>> 单词合成问题 (经典算法题500道)
### 题目描述补充
**单词合成问题**：
给定一个字符串数组 `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 示例代码
```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 示例代码
```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 示例代码
```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
```
**码小课**网站中有更多关于算法和数据结构的内容分享，包括动态规划、字符串处理、搜索算法等，欢迎大家学习交流。