29 ms CPP simple solution. No KMP.


  • 22
    S
    class Solution {
    public:
        bool repeatedSubstringPattern(string str) {
            string nextStr = str;
            int len = str.length();
            if(len < 1) return false;
            for(int i = 1; i <= len / 2; i++){
                if(len % i == 0){
                    nextStr = leftShift(str, i);
                    if(nextStr == str) return true;
                }
            }
            return false;
        }
        
        string leftShift(string &str, int l){
            string ret = str.substr(l);
            ret += str.substr(0, l);
            return ret;
        }
    };
    

  • 15

    Ooh, very nice. Avoids having to multiply a string, which is annoying in C++ and Java. Here's a variation:

    Java:

    public boolean repeatedSubstringPattern(String str) {
        int n = str.length();
        for (int i = 1; i <= n / 2; i++)
            if (n % i == 0 && str.startsWith(str.substring(i)))
                return true;
        return false;
    }
    

    C++:

    bool repeatedSubstringPattern(string str) {
        int n = str.length();
        for (int i = 1; i <= n / 2; i++)
            if (n % i == 0 && str.substr(i) == str.substr(0, n - i))
                return true;
        return false;
    }

  • 0
    C

    @StefanPochmann How did you come up with such concise solution? Thanks


  • 0

    @coder2 That's pretty much still @xiadong1994731's solution. I just removed the fluff and made a minor change (checking suffix against prefix instead of rotation against original).


  • 0

    brilliant solution


  • 0

    How you come up with this solution at first place, this is a really really clever observation.


  • 0
    C

    Is the time complexity still O(n^2) ? Because the substr function may be O(n)? Thanks


  • 0
    S

    @coder2 I think this is not O(n^2), because only when the length of substring i is the factor of the length of str we will use substr function.


  • 0
    R

    nice thought!


  • 0
    R
    This post is deleted!

  • 0

    This is nice solution, although it might not actually change the running time of the solution, the code certainly looks much nicer.

    In the original naive implementation (interval by inerval comparison)
    For each i that passes the n % i == 0 test: for each j = 0..i, we confirm that str.charAt(j) repeats itself n / i - 1 times afterwards, which takes n / i - 1 comparisons. Thus the number of character comparisons done in each iteration would be i * (n / i - 1) = n - i.

    In this improved version, if we suppose that the JVM still does character-by-character comparison to implement startsWith, then there would be n - i character comparisons for each i as described above. This is for @StefanPochmann 's solution. In this case, the running time stayed unchanged.
    In the case of @shell32 's implementation, we actually have to do n character comparisons for each qualifying i because he chose to append the str[0:i] back to the shifted string. That means the running time actually increased.

    But again, I am not sure whether JVM has some special tricks for String STL implementations. If they do, then these versions are definitely better.


Log in to reply
 

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