小米面试题：单词拆分

题目：
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

示例 2：

输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。注意你可以重复使用字典中的单词。

示例 3：

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

解题方案：动态规划

//单词拆分 //wordDict 单词字典 //dp[i] 表示前一个字符能否被拆分成功字典中出现的单词 //s 是源字符串 func wordBreak(s string, wordDict []string) bool {//定义一个mapwordDictSet := make(map[string]bool)for _, w := range wordDict {wordDictSet[w] = true //key是每个单词}dp := make([]bool, len(s) + 1)dp[0] = truefor i := 1; i <= len(s); i++ {for j := 0; j < i; j++ {if dp[j] && wordDictSet[s[j:i]] {dp[i] = truebreak}}}return dp[len(s)] }

依次遍历0~i之间的字符串，每次判断0~i之间的字符串是否满足字典里面的要求。d[j]保留了前j字符对应的状态，wordDictSet[s[j:i]]为最后一个字符串的状态，最后一个字符串前面所有的字符串都可以通过d[j]来判断是否满足条件。
如果有匹配，则返回对应dp下标对应的状态。

时间复杂度：O(n^2)
空间复杂度：O(n)

 

 

参考地址：https://leetcode-cn.com/problems/word-break/solution/dan-ci-chai-fen-by-leetcode-solution/

 

 

 

总结

以上是生活随笔为你收集整理的小米面试题：单词拆分的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。