[23ms] C++ sln, dp + DFS


  • 0
    L
    class Solution {
    public:
    vector<string> wordBreak(string s, vector<string>& wordDict) 
    {
        
        for(auto s:wordDict)
        {
            dict.insert(s);
        }
        int len = s.size();
        
        vector<vector<bool>> T(len,vector<bool>(len,false));
        // scan different length of substring, start from 1 (bottom) to len(top), bottom-up dp sln
        for(int l = 1; l<=len; l++) 
        {
            for(int i = 0; i<=len-l; i++)
            {
                // i is the row index and j is the column index of the table T
                // meaning currently we are solve subproblem of substring s[i:j]
                int j = i+l-1;  
                // get the substring with lenght l: s[i:j]
                string tps = s.substr(i,l);
                if(dict.find(tps)!=dict.end())
                    T[i][j] = true;
                else
                    for(int k = i;k<j;k++)
                        if(T[i][k]==true && T[k+1][j]==true)
                        {
                            T[i][j] = true;
                            break;
                        }
            }
        }
        string temp = "";
        reconSln(s,temp,T,0);
        return memory;
    }
    private:
    vector<string> memory;
    unordered_set<string> dict;
    
    // reconstruct the solution of the dp, with DFS
    // string s is the original string, temp is a helper variable for recursive method
    void reconSln(string s, string temp,vector<vector<bool>> T, int depth)
    {
        int col = T[0].size();
        for(int i = depth; i<col; i++)
            if (T[depth][i] == true && dict.count(s.substr(depth,i-depth+1)))
            {
                // DFS
                if(i!=col-1)
                { 
                    string p = temp + s.substr(depth,i-depth+1) + " ";
                    // iff T[i+1][col-1]==true, that branch may have a solution
                    if(T[i+1][col-1]==true)
                        reconSln(s,p,T,i+1);
                }
                else // bottom of DFS
                {
                    
                    string rs = temp + s.substr(depth); // the last word of the string
                    memory.push_back(rs);
                }
            }
    }
    };

Log in to reply
 

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