LeetCode [459] Repeated Substring Pattern

459. Repeated Substring Pattern

Easy

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

 

Example 1:

Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.

Example 2:

Input: "aba"
Output: False

Example 3:

Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution { public boolean repeatedSubstringPattern(String s) { int n = s.length(), i = 1; int[] dp = new int[n]; while(i<n){ int l = dp[i-1]; while(l>0 && s.charAt(i)!=s.charAt(l)){ l = dp[l-1]; } if(s.charAt(i)==s.charAt(l)){ dp[i] = l+1; } i++; } if(dp[n-1]==0) return false; int lenRepeat = n-dp[n-1]; return n%lenRepeat==0; } }

YMSF

abcabc 3 pattern是abc, 整个str可以repeat ,返回true

abababab 4 pattern是abab,整个str可以repeat, 返回 true

abcabc 2 pattern是ab,整个str不能repeat, 返回false

写完后要求不用extra memory ，然后问如何求出最长的repeat pattern, 讲了brute force,从大到小，要求优化，发现试common denominator 的长度即可，但面试官说不是最优解

 

至少重复出现两次