Why am I getting WA

  • 0

    The Idea is to start from s[0] and find all possible matches of s.substr(0 ..... n).
    Then start from s[1] and check if s[1] reachable using strings from the dictionary.
    if it is, then find all possible reachable indexes and flag them.
    do this for s[2] ... s[n].

    if s[n] is flagged, return true else false.

    class Solution {
        bool wordBreak(string s, vector<string>& wordDict) {
            vector<bool> dp(wordDict.size(), false);
            dp[0] = true;
            for(int i = 0; i < s.size(); ++i)
                    for(int j = 1; j <= s.size() - i; ++j)
                        if(contains(wordDict, s.substr(i, j)))
                            dp[i + j] = true;
            return dp[s.size()];
        bool contains(vector<string> &wordDict, string s){
            for(auto &x : wordDict)
                if(x.compare(s) == 0) return true;
            return false;

Log in to reply

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