当前位置: 面试刷题>> 单词拆分 (经典算法题500道)
### 题目描述
**单词拆分**:给定一个非空字符串 `s` 和一个包含非空单词的列表 `wordDict`,判定 `s` 是否可以被空格拆分成一个或多个在字典中出现的单词。
**说明**:
- 你可以假设字典中没有重复的单词。
- 你可以假设 `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) {
$wordSet = array_flip($wordDict); // 将单词列表转换为哈希集合以提高查找效率
$n = strlen($s);
$dp = array_fill(0, $n + 1, false); // dp[i] 表示 s 的前 i 个字符是否能被拆分成单词
$dp[0] = true; // 空字符串总是可以被拆分
for ($i = 1; $i <= $n; $i++) {
for ($j = 0; $j < $i; $j++) {
if ($dp[$j] && isset($wordSet[substr($s, $j, $i - $j)])) {
$dp[$i] = true;
break;
}
}
}
return $dp[$n];
}
```
### Python 代码示例
```python
def wordBreak(s, wordDict):
wordSet = set(wordDict) # 将单词列表转换为集合以提高查找效率
n = len(s)
dp = [False] * (n + 1) # dp[i] 表示 s 的前 i 个字符是否能被拆分成单词
dp[0] = True # 空字符串总是可以被拆分
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in wordSet:
dp[i] = True
break
return dp[n]
```
### JavaScript 代码示例
```javascript
function wordBreak(s, wordDict) {
const wordSet = new Set(wordDict); // 将单词列表转换为集合以提高查找效率
const n = s.length;
const dp = new Array(n + 1).fill(false); // dp[i] 表示 s 的前 i 个字符是否能被拆分成单词
dp[0] = true; // 空字符串总是可以被拆分
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordSet.has(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
```
**码小课**:以上代码示例展示了如何使用动态规划(Dynamic Programming, DP)解决单词拆分问题。在码小课网站上,你可以找到更多关于算法和数据结构的详细解析和练习,帮助你进一步提升编程能力。