题目描述

给定一个非空字符串$s$和一个非空词典$wordDict$,判断$s$是否能被分割成一个或多个单词分隔的序列。

注意，词典中的词可以用多次，词典中没有重复的单词。

样例

Example 1:

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释:  "leetcode" 可以被切割成 "leet code"

Example 2:

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: "applepenapple" 可以被切割成 "apple pen apple"

Example 3:

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

算法1 动态规划

Time $O(n^2)$, Space $O(n)$

用一个bool数组$dp[i]$表示$s[0:i]$是否能被break，例如$dp[1]$表示$s[0:1]$也就是$s[0]$单独一个字母是可以break的。

1. 构造集合unordered_set， 因为题目给的“词典”是vector不是set， 查找起来不好用。
2. 遍历数组$s$，判断有没有某个断点$j$刚好可以满足$s[j,i]$在词典中
3. 返回$dp[s.size()]$，表示$s[0:s.size()]$是否为断点

Time $O(n^2)$：两层for loop

Space $O(n)$： unordered_set和vector

C++ 代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end()); //构建为set，方便查找

        vector<bool> dp(s.size()+1, false); //dp表示字符之间的隔板，n个字符有n+1个隔板
        dp[0] = true; //dp[0]是s[0]前面的隔板

        for(int i=1; i<=s.size(); ++i){
            for(int j=i; j>=0; --j){
                if(dict.find(s.substr(j,i-j))!=dict.end() && dp[j]){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};