Is complexity really quadratic?


  • 0
    H

    Hi, I was wondering if the accepted solutions (or any solution at all) should be considered as quadratic, as a look-up in a set of strings should take linear time on the size of the looked string (for a hash set) or even log-linear time for a tree set.

    Therefore, in my opinion, the total time complexity should be cubic.

    Any thoughts on that?

    Here goes my solution in C++ using memoization.

        bool wordBreak(string s, vector<string>& wordDict) {
            set<string> wordSet( wordDict.begin(), wordDict.end() );
            int n = s.length();
            vector<int> validIndices = {0};
            for(int i=1; i<=n; i++) {
                for(auto j : validIndices) {
                    if(wordSet.find(s.substr(j, i-j)) != wordSet.end()) {
                        validIndices.push_back(i);
                        break;
                    }
                }
            }
            return validIndices[validIndices.size()-1] == n;
        }
    

Log in to reply
 

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