当前位置: 面试刷题>> 单词拆分 (经典算法题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)解决单词拆分问题。在码小课网站上,你可以找到更多关于算法和数据结构的详细解析和练习,帮助你进一步提升编程能力。
推荐面试题