C++ 12ms dp solution

  • 4

    The flag can be used to save repetitive examinations of of bad substrs.

    class Solution {
    void helper(vector<bool>& flag, string s, int n, string pre, vector<string> &res, unordered_set<string>& wordDict){
        if (n>=s.size()) {res.push_back(pre);return;}
        for (int i=n;i<s.size();i++){
            if (flag[i+1] && wordDict.find(s.substr(n,i-n+1))!=wordDict.end()){
                helper(flag,s,i+1,pre+s.substr(n,i-n+1)+" ",res,wordDict);
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        vector<string> res;
        if (s.empty()) {res.push_back("");return res;}
        int k=s.size();
        vector<bool> flag(k+1,0);
        flag[k] = 1;
        for (int i=k-1;i>=0;i--){
            int j=i;
                if (flag[j+1] && wordDict.find(s.substr(i,j-i+1))!=wordDict.end()){
                    flag[i] = 1;break;
        if (flag[0]==0) return res;   // no possible solution if flag[0]==false
        helper(flag,s,0, "",res,wordDict);
        for (auto &s:res){
        return res;

  • 0

    can you explain your solution?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.