Evolve from brute force to optimal


  • 4
    1. O(n^3) check each substr, a hashtable is used to remove duplicate strings.
        int findSubstringInWraproundString(string p) {
            int n = p.size();
            unordered_set<string> ht;
            for(int i=0;i<n;i++)
                for(int j=i;j<n;j++) {
                    if(j>i && p[j-1]+1!=p[j] && p[j-1]-p[j]!=25) break;
                    ht.insert(p.substr(i,j-i+1));
                }
            return ht.size();
        }
    
    1. O(n^2 logn), Each valid substr can be represented by the first char and the length, instead of the whole string.
        int findSubstringInWraproundString(string p) {
            int n = p.size();
            set<pair<char,int>> bst;
            for(int i=0;i<n;i++)
                for(int j=i;j<n;j++) {
                    if(j>i && p[j-1]+1!=p[j] && p[j-1]-p[j]!=25) break;
                    bst.insert(pair<char,int>(p[i],j-i+1));
                }
            return bst.size();
        }
    
    1. O(n^2). For substrs starting at the same char, we only need to record the longest one. Because it covers all the shorter substrs starting from the char. The length is the number of substrings starting at the char.
        int findSubstringInWraproundString(string p) {
            int n = p.size(), len[26]={0};
            for(int i=0;i<n;i++)
                for(int j=i;j<n;j++) {
                    if(j>i && p[j-1]+1!=p[j] && p[j-1]-p[j]!=25) break;
                    len[p[i]-'a'] = max(len[p[i]-'a'],j-i+1);
                }
            return accumulate(len,len+26,0);
        }
    
    1. O(n). Getting the longest substr starting from each char can be done in linear time. We can use two pointers to keep track of the current valid substring.
        int findSubstringInWraproundString(string p) {
            int len[26]={0}, i = 0, n = p.size();
            for(int j=0;j<n;j++)
                if(j>i && p[j-1]+1!=p[j] && p[j-1]-p[j]!=25) {
                    for(int k=i;k<min(j,i+26);k++) len[p[k]-'a'] = max(len[p[k]-'a'],j-k);
                    i=j--;
                }
            for(int k=i;k<min(n,i+26);k++) len[p[k]-'a'] = max(len[p[k]-'a'],n-k);
            return accumulate(len,len+26,0);
        }
    

  • 0
    S

    Cool, optimize it step by step!


Log in to reply
 

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