0ms DP solution


  • 1
    Z

    dp[i] means whether string ends at position i valid.

    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string>& wordDict) {
            if( s.empty() || wordDict.empty() ) {
                return false;
            }
            
            vector<int> dp(s.size() + 1, 0);
            dp[0] = 1;
            for(int i = 1; i <= s.size(); ++i) {
                for(int j = i - 1; j >= 0; --j) {
                    if( dp[j] && wordDict.find(s.substr(j, i - j)) != wordDict.end() ) {
                        dp[i] = 1;
                        break;
                    }
                }
            }
            
            return dp[s.size()];
        }
    };

Log in to reply
 

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