当前位置： 面试刷题>> 单词拆分(经典算法150题)
### 题目描述
**单词拆分**
给定一个非空字符串 `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 代码示例
```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 代码示例
```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 代码示例
```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`。在面试中，能够清晰地解释算法思路和展示代码能力是非常重要的。