Time Limit Exceeded


  • 3
    N

    Last executed input:
    s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";

    dict = {"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"}

    Here is my code:

    class Solution {
    public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        if (dict.empty()) return false; //dictionary is empty 
        unordered_set<string>::const_iterator match = dict.find(s);
        if (match != dict.end()) return true; //the whole string is one dictionary word
        
        for (unsigned int i = 1; i <= s.length(); i++){
            string str = s.substr(0, i); //first substring of s from beginning to position i
            match = dict.find(str);
            if (match != dict.end()){
                //if first substring is a dictionary word
                //get the second substring which is the remaining part of string s
                //if second substring is empty, return true
                //else recursively call wordBreak on the second substring
                string str2 = s.substr(i);
                if (str2.empty()) return true;
                else if (wordBreak(str2, dict)) return true;
                //substring doesn't fit, continue iterating, increase i by 1
            }
        }
        //after iterating through the whole string, not match found, return false
        return false;
    }
    };

  • 4
    S

    You solve it by recursion. But it is not the best solution. Since the time complexity would be large.

    You may think about using DP to solve it.


  • 3
    W

    O(n^2) solution:

    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string> &dict) {
            size_t length = s.size();
            vector<vector<bool>> record(length, vector<bool>(length, false));
            
            for(size_t i = 0; i < length; ++i){
                for(size_t len = 0; len < length - i; ++len){
                    string subword = s.substr(i,len+1);
                    if(dict.find(subword) != dict.end()){
                        record[i][len] = true;
                        if(i > 0 && record[0][i-1]) record[0][i+len] = true;
                    }
                }
            }
            
            return record[0][length-1];
        }
    };

  • 0
    S

    Could you please update your answer with some words explain your algorithm?


  • 0
    N

    Yeah, that should be the case. But do you think there is any problem with my coding disregarding the time complexity issue? I will try out DP to solve this problem even though I have no clue how to. Thank you!


  • 0
    W

    what is the complexity of dict.find(sub word)?


Log in to reply
 

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