C++ Solution O(n* sqrt(n) )


  • 0
    A

    The idea , is check each possible prefix, see if its multiple concatenation , could result in the original string , for this the length of the prefix should be a factor of the length of the original string ,
    there are atmost sqrt(n) factor for a given numbers.

    class Solution {
    public:
        bool repeatedSubstringPattern(string str) {
            int i,j,k,n;
            bool temp_ans;
            n = str.size();
            for(i=1;i<n;i++)
            {
                if(n%i == 0)
                {
                temp_ans = true;
                    for(j=0;j<n;j++)
                        if(str[j]!=str[j%i])
                        {
                            temp_ans = false;
                            break;
                        }
                if(temp_ans)
                    return true;
                }
            }
            return false;
        }
    };
    

Log in to reply
 

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