高频算法面试题（字符串） leetcode 139. 单词拆分

leetcode 139. 单词拆分

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

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

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
复制代码

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

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
复制代码

这道题，我们考虑用动态规划的做法。我们每次考虑字符串从开始的当前索引位置是否可以被拆分。如果可以就记忆化方便下次使用。走起：

func wordBreak(s string, wordDict []string) bool {
 //首先先把所有的单词存到Map中，利用hash的O(1)的查找时间复杂度
    m := make(map[string]bool, len(wordDict))
    for _, v:= range wordDict {
        m[v] = true
    }
    //初始化dp数组
    dp := make([]bool, len(s)+1)
    dp[0] = true
    for i:=1;i<=len(s);i++ {
        for j:=0;j<i;j++ {
        //每次可以看前j个元素，和从j到i是否可以被拆分。
            if dp[j] && m[s[j:i]] {
            //dp数组中记忆化，方便下轮循环查看（这里的i表示是当前是第几个元素，并非是索引下标）
                dp[i] = true
                break
            }
        }
    }
    //返回dp数组最后一个元素就好
    return dp[len(s)]
}
复制代码

动态规划是典型的纸老虎，看起来很唬人，但是它是吃草的哦。多玩玩就有感觉了。继续加油。

算法梦想家，来跟我一起玩算法，玩音乐，聊聊文学创作，咱们一起天马行空！

转载于:https://juejin.im/post/5cc172a75188252d8b3ad509