C++ solution(4ms)


  • 1
    C

    When a string is given, try to break it by every word in the dictionary, and got the corresponding part except the word. And then break the part again by every word. Until one of the result part is empty, we know the string can be break.

    We find that we don't care which words compose the substring, we just care whether the substring can be break. So an array Sub[i] is used to record whether substring from 0 to i-1 can be break. if Sub[i] is true, try every word in the dictionary to match the substring from i to i+wordLength. if Sub[i] is false, the trial is meaningless.

    bool wordBreak(string s, unordered_set<string>& wordDict) {
        if (s.length() < 1){
            return false;
        }
        
        vector<bool> sub(s.length() + 1);
        sub[0] = true;
        
        for (int i = 0; i < s.length(); i++){
            if (!sub[i]) {continue;}
            
            for (string word : wordDict){
                int end = i + word.length();
                if(end > s.length() || sub[end]){
                    continue;
                }
                
                if (s.substr(i, word.length())==word){
                    sub[end] = true;
                }
                
            }
            
        }
        
        return sub[s.length()];
    
    }

Log in to reply
 

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