C++ 26ms beat 97% with explanations


  • 0
    H

    The problem is to check if a string s can be constructed by repeating another string p at least twice.
    If it is true, it is obvious that p must start with s[0] and end with s[s.size()-1]. Then we check all sub strings p in s which meet this condition to see if s is multiple repeats of p. To speed up:

    1. s.size() % p.size() must be zero
    2. if p.size() > s.size() / 2, result is obvious false.
        bool repeatedSubstringPattern(string str) {
            int n = str.size();
            int pos = 0;
            while (pos <= n/2) {
                int len = str.find(str[n-1], pos) + 1;
                if (len > n/2) return false;
                if (n % len == 0) {
                    string p = str.substr(0, len);
                    bool match = true;
                    for (int i = len; i < n; i += len) {
                        if (str.substr(i, len) != p) {
                            match = false;
                            break;
                        }
                    }
                    if (match) return true;
                }
                pos = len;
            }
            return false;
        }
    

Log in to reply
 

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