题目描述补充
单词合成问题:
给定一个字符串数组 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
码小课网站中有更多关于算法和数据结构的内容分享,包括动态规划、字符串处理、搜索算法等,欢迎大家学习交流。