Why am I getting WA


  • 0
    P

    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 {
    public:
        bool wordBreak(string s, vector<string>& wordDict) {
            vector<bool> dp(wordDict.size(), false);
            dp[0] = true;
            for(int i = 0; i < s.size(); ++i)
            {
                if(dp[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.