6-line C++ solution with prime factor check


  • 0

    Inspired by @jinyao 's Java solution with building prime table, the key here is that only need to check number of subsegments nSeg which is a prime divisor of s.length(). Because if s can be partitioned into nSeg identical substrings, it can be definitely partitioned into nSeg/d longer substrings which are concatenation of d smaller substrings each.

        bool repeatedSubstringPattern(string s) {
          int n = s.size(); vector<bool> prime(n+1, true);
          for (int i = 2; i <= n; ++i) {
            if (n%i || !prime[i]) continue;
            if (s.substr(n/i) == s.substr(0, n-n/i)) return true;
            for (int j = 2; i*j <= n; ++j) prime[i*j] = false;
          }
          return false;
        }
    

Log in to reply
 

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