8ms DP solution in C++


  • -1
    D
    class Solution {
    public:
    
    unordered_map<int , vector<string>> dpHash2;
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            vector<string> ans;
            if (wordDict.size() == 0) return ans;
            // handle 1) suffix not match: "aa...ab" and 2) prefix not match: "ba...aa"
            bool match = false;
            for (int i = (int)s.size()-1; i>=0; i--){
                if (wordDict.count(s.substr(i))) {
                     match = true;
                     break;
                }
            }
            if (!match) return ans;
            
            for (int i = 1; i<s.size(); i++){
                if (wordDict.count(s.substr(0,i))) {
                     match = true;
                     break;
                }
            }
            if (!match) return ans;
            // DP
            vector<bool> found(s.size()+1, false);
            found[0] = true;
            dpHash2[0].push_back("");
            for (int i = 1; i<= s.size(); i++){
                for (int j=0; j < i; j++){
                    string word = s.substr(j,i-j);
                    if (found[j] && wordDict.count(word)){
                        found[i] = true;
                        for (auto it:dpHash2[j]){
                            string new_string = (j == 0) ? word : it + " " + word;
                            dpHash2[i].push_back(new_string);
                        }
                    }
                }
            }
            for (auto it:dpHash2[(int)s.size()]){
                ans.push_back(it);
            }
            return ans;
        }
    }

  • 0
    N

    if (!match) return ans;

        for (int i = 1; i<s.size(); i++){
            if (wordDict.count(s.substr(0,i))) match = true;
        }
        if (!match) return ans;
    

    is obviously wrong, by the time you get to the second loop, match is already true and why are you doing another one? Also, you can break in the first loop after true.


  • 0
    X

    I think he wants to do some pre processing as if there are no dictionary words at the begin or the end of the string, return. But I agree with you that first match shall be reset and the loop can be break after finding one word.


  • 0
    D

    Thanks! I've added 'break' within the for loop once a match is found


  • 0
    N

    Glad that I can help, actually you do not need the second loop at all.


Log in to reply
 

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