I want to optimize my solution with some better idea rather than this tricky method.Anyone can help?


  • 0
    Z

    actually, i got an accepted using a solution which has the O(n^3) time-complexity . of course there is a tricky method in it. Is there anybody could help me to reduce its time-complexity?THANKS.
    comment:DP[i][j] is a bool array which means whether we can make a matching in that dictionary using s[i~j].

    class Solution {
    public:
    list <string> seg;
    bool dp[500][500];
    void recursion(int left, int right, string s, int len, vector<string> &ans)
    {
         if (right == len-1){
            string per_ans = "";
            for (list<string> :: iterator it = seg.begin(); it != seg.end(); it ++){
                if (it != seg.begin())per_ans += " ";
                   per_ans += (*it);
                }      
            ans.push_back(per_ans);
         } 
         for (int i = right+1; i < len; i ++){
             if (dp[right+1][i]){
                seg.push_back(s.substr(right+1, i-right));
                recursion(right+1, i, s, len, ans);
                seg.pop_back();                    
             }    
         }    
    }
    
    
        vector<string> wordBreak(string s, unordered_set<string> &dict) {
             int len = s.length();
             vector<string> ans;
             ans.clear();
             for (int i = 0; i < len; i ++){
                 for (int j = 0; j < len; j ++)  dp[i][j] = false;
                 if (dict.find(s.substr(0,i+1)) != dict.end())dp[0][i] = true;
             }
             for (int i = 0; i < s.length(); i ++){
                 for (int j = 0; j < len; j ++){
                     if (dp[i][j]){
                        for (int k = j+1; k < len; k ++){
                            if (dp[j+1][k] == false && dict.find(s.substr(j+1, k-j)) != dict.end())dp[j+1][k] = true;    
                        }                
                     }    
                 }    
             }
             bool jud = true;//so tricky, if there has no matching of dictionary return the initial vector
             for (int i = 0; i < len && jud; i ++){
                if (dp[i][len-1])jud = false;    
             }
             if (jud)return ans;
             for (int i = 0; i < len; i ++){
                 if (dp[0][i]){
                    seg.push_back(s.substr(0,i+1));
                    recursion(0,i,s,len,ans);
                    seg.pop_back();
                 }  
             }
             return ans;
        }
    };

Log in to reply
 

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