LeetCode 459 - Repeated Substring Pattern


http://bookshadow.com/weblog/2016/11/13/leetcode-repeated-substring-pattern/
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.)
X. 
  1. First char of input string is first char of repeated substring
  2. Last char of input string is last char of repeated substring
  3. Let S1 = S + S (where S in input string)
  4. Remove 1 and last char of S1. Let this be S2
  5. If S exists in S2 then return true else false
  6. Let i be index in S2 where S starts then repeated substring length i + 1 and repeated substring S[0: i+1]
The maximum length of a "repeated" substring that you could get from a string would be half it's length
For example, s = "abcdabcd", "abcd" of len = 4, is the repeated substring.
You cannot have a substring >(len(s)/2), that can be repeated.
  1. So, when ss = s + s , we will have atleast 4 parts of "repeated substring" in ss.
  2. (s+s)[1:-1], With this we are removing 1st char and last char => Out of 4 parts of repeated substring, 2 part will be gone (they will no longer have the same substring).
  3. ss.find(s) != -1, But still we have 2 parts out of which we can make s. And that's how ss should have s, if s has repeated substring
首先证明充分性:
不妨设S = X1,X2...Xn,则X1X2...Xn∈X2...XnX1...Xn-1,令从Xi处开始匹配(2<=i<=n)
则Xi...XnX1...Xi-1 = X1X2...Xn,令Xi...Xn = a, X1...Xi-1 = b,则ab = ba,则a = b,所以S = aa,所以S可由a重复两次得到。
必要性类似可证

One way to think about this one-line Java solution return (s+s).substring(1,2*s.length()-1).indexOf(s)!=-1; is interleaving. Since we get rid of head and tail, if we still find the whole string in s+s, it must start from the left s string, cover the entire intersection of s and s, and end in the right s string since otherwise the length would not be enough. 

Then we could move the whole piece parallel to left and right correspondingly to cover the start and end which we hided. Then the left uncovered part must = the first part in the whole string we found in s+s. Thus in the original string, we have the first two part the same, then we could use transitive rule to generalize this pattern to the whole string (the back to start has the same logic)
Let’s say T = S + S.
“S is Repeated => From T[1:-1] we can find S” is obvious.
即只要我们在T[1:-1]中可以找到S,S便为重复的。
下面是关于这句话的证明的翻译:
  • 如果在T[1:-1]中可以找到S,且index为p-1, 那么在T和S中的index为p
  • s1 = S[:p]S可以被表示为s1X1, 因为S为重复字符串,所以S = X1s1 = s1X1 (A)
    1. len(X1) < len(s1)
      这种情况不存在,以为如果我们发现ST[1:-1],则index应为len(X1),而不是len(s1) = p
    2. len(X1) == len(s1)
      由A式可以推出X1 = s1,则S为重复的
    3. len(X1) > len(s1)
      因为A式,X1有前缀s1,可以表示为s1X2
      X1 = s1X2,由A式得到s1s1X2 = s1X2s1, 即X2s1 = s1X2 (B)
      这下就简洁明了了,依照前面的步骤递推,最终我们可以得到一个Xnlen(Xn) == len(s1) 并且 Xns1 = s1Xn => Xn = s1 => S = s1X1 = s1s1X2 = ... = s1s1...s1Xn-1 = s1s1...s1s1Xn => S is Repeated.
public boolean repeatedSubstringPattern(String str) {
        String s = str + str;
        return s.substring(1, s.length() - 1).contains(str);
}
  • double现在的string
  • 去掉头和尾巴(因为如果有substring,第一个肯定是substring的头部,最后一个肯定是他的尾部)
  • 然后看double的string是否包含老的string(如果重复老string至少有2个substring,新的至少4个,去除掉了头和尾,刚好剩下两个(如果原先三次,则新的会有4个),所以肯定包含)

X. KMP
KMP算法对于next数组的应用。
next[i]是指对于字符串s[0,i-1]中,前缀与后缀的最大匹配长度。
例如对于"abcabcabc"来说,其next[8] = 5,也即对于s[0,7]="abcabcab",前缀与后缀最大匹配的串为"abcab",长度为5。
用字符串长度减1减去最后一位的next数组值之后得到的应为重复串的长度
    public boolean repeatedSubstringPattern(String s) {
        int l = s.length();
        int[] next = new int[l];
        next[0] = -1;
        int i, j = -1;
        for (i = 1; i < l; i++) {
            while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
                j = next[j];
            }
            if (s.charAt(i) == s.charAt(j + 1)) {
                j++;
            }
            next[i] = j;
        }
        int lenSub = l - 1 - next[l - 1];
        return lenSub != l && l % lenSub ==0;
    }
  • 1


下面这种方法是参考的网上的这个帖子,原作者说是用的KMP算法,LeetCode之前也有一道应用KMP算法来解的题Shortest Palindrome,但是感觉那道题才是KMP算法。这道题也称为KMP算法感觉怪怪的(关于KMP的详细介绍请参见从头到尾彻底理解KMP,也可以看博主自己写的一篇KMP Algorithm 字符串匹配算法KMP小结),KMP算法中的next数组是找当前位置的最大相同前缀后缀的个数,而这道题维护的一位数组dp[i]表示,到位置i-1为止的重复字符串的字符个数,不包括被重复的那个字符串,什么意思呢,我们举个例子,比如"abcabc"的dp数组为[0 0 0 0 1 2 3],dp数组长度要比原字符串长度多一个。那么我们看最后一个位置数字为3,就表示重复的字符串的字符数有3个。如果是"abcabcabc",那么dp数组为[0 0 0 0 1 2 3 4 5 6],我们发现最后一个数字为6,那么表示重复的字符串为“abcabc”,有6个字符。那么怎么通过最后一个数字来知道原字符串是否由重复的子字符串组成的呢,首先当然是最后一个数字不能为0,而且还要满足dp[n] % (n - dp[n]) == 0才行,因为n - dp[n]是一个子字符串的长度,那么重复字符串的长度和肯定是一个子字符串的整数倍
    bool repeatedSubstringPattern(string str) {
        int i = 1, j = 0, n = str.size();
        vector<int> dp(n + 1, 0);
        while (i < n) {
            if (str[i] == str[j]) dp[++i] = ++j;
            else if (j == 0) ++i;
            else j = dp[j];
        }
        return dp[n] && (dp[n] % (n - dp[n]) == 0);
    }d
解法I KMP算法
时间复杂度 O(n)
记字符串长度为size

利用KMP算法求next数组,记next数组的最后一个元素为p

若p > 0 并且 size % (size - p) == 0,返回True

next数组具有如下性质:

str[ 0 : next[i] ] == str[ i + 1 - next[i] : i + 1 ]

例如:

a, b, c, d, a, b, c, a, b, c, d, a, b, c, d, c

0, 0, 0, 0, 1, 2, 3, 1, 2, 3, 4, 5, 6, 7, 4, 0

首先如果字符串的字母数小于两个,那也不用判断了,一定不可能是多个子字符串重复出来的。

设立两个标记,一个快一点一个慢一点。快的从第二个字母开始往后遍历,找到与第一个字母一样的,就停下来开始判断,慢的从第一个字母开始,两个标记一起往后遍历,看是不是可以完全一致,一直到最后一个字母,如果从后面开始的与从头开始的一模一样,说明是存在重复的字符串,并且由它重复组成的。

如果遍历时又出现不一样了,这时候说明还不是重复的,就要继续当做从头开始找了,继续往后遍历快的标记,找与第一个字母一样的,然后重复上面的过程,注意找到后慢的标记需要回到第一个字母。

不管找没找到,当快的遍历到最后字母了就停止遍历了,这时如果是没找到的状态,那就直接false了,如果是找到的状态,那么有可能是确实重复组成的,也有可能只是最后一小节和前面的一样,中间的一段还是没有重复的,这时候根据慢的标记来判断,如果慢的标记已经走过了整个字符串的一半,就说明至少是二分之一的子字符串重复两次得到的,或者更小的字符串重复多次。如果慢的标记还没走过一半,说明中间还有一部分并没有来得及重复,这时候就依然是false了。在判断慢的是否过半了时,由于存在整个字符串长度可能为基数也可能为偶数的情况,所以用慢标记的位置乘以二来和整体长度作比较进行判断比较合适。

这个方法只需要遍历一次字符串,时间复杂度只有O(n),还是很快的,实际结果也打败了95%的人~
    public boolean repeatedSubstringPattern(String str) {
        if (str.length() < 2) return false;

        char[] arr = str.toCharArray();
        int low = 0;
        int fast = 1;
        boolean match = false;// 匹配到与否的标记
        while (fast < arr.length) {
            if (arr[fast] == arr[0]) {
                // 匹配到了第一个,开始判断是否重复
                for (low = 0; fast < arr.length;) {
                    if (arr[low] == arr[fast]) {// 往后走进行不断判断
                        match = true;
                        low++;
                        fast++;
                    } else {// 匹配不一致,跳出去重新找
                        match = false;
                        break;
                    }
                }
            } else {// 没能匹配首字母
                match = false;
                fast++;
            }
        }
        return match && low*2 >= arr.length;
    }


X. O(n^2) solution
这道题给了我们一个字符串,问其是否能拆成n个重复的子串。那么既然能拆分成多个子串,那么每个子串的长度肯定不能大于原字符串长度的一半,那么我们可以从原字符串长度的一半遍历到1,如果当前长度能被总长度整除,说明可以分成若干个子字符串,我们将这些子字符串拼接起来看跟原字符串是否相等。 如果拆完了都不相等,返回false
https://leetcode.com/problems/repeated-substring-pattern/discuss/94352/Java-Simple-Solution-with-Explanation
public boolean repeatedSubstringPattern(String str) {
 int l = str.length();
 for(int i=l/2;i>=1;i--) {
  if(l%i==0) {
   int m = l/i;
   String subS = str.substring(0,i);
   StringBuilder sb = new StringBuilder();
   for(int j=0;j<m;j++) {
    sb.append(subS);
   }
   if(sb.toString().equals(str)) return true;
  }
 }
 return false;
}
  1. The length of the repeating substring must be a divisor of the length of the input string
  2. Search for all possible divisor of str.length, starting for length/2
  3. If i is a divisor of length, repeat the substring from 0 to i the number of times i is contained in s.length
  4. If the repeated substring is equals to the input str return true
public boolean repeatedSubstringPattern(String str) {
if(str == null || str.length() <= 1) return false;
int len = str.length();
for ( int i=0; i<=len/2; i++) {
boolean flag = true;
if (len%(i+1) != 0 || len == i+1) continue;
String subString = str.substring(0,(i+1));
int start = i+1;
int end = start * 2;
while (end<=len) {
if (!subString.equals(str.substring(start,end))){
flag = false; break;
}
start = start + i+1;
end = end + i+1;
}
// System.out.println(flag);
if (flag) return true;
}
return false;
}
遍历所有n的约数,然后依次与原字符串进行比较。
我的做法是假设约数为m,那么可以每次比较原字符串的m个字符,看是否一致,如果都一致,则返回True,循环结束。
具体代码如下:
public boolean repeatedSubstringPattern(String s) {
    char[] charS = s.toCharArray();
    int n = charS.length;
    for (int i = n / 2; i >= 1; i--) {
        if (n % i == 0) {
            boolean temp = false;
            for (int j = i; j < charS.length; j = j + i) {
                for (int k = j; k < j + i; k++) {
                    if (charS[k] != charS[k - i]) {
                        temp = true;
                        break;
                    }
                }
                if (temp) {
                    break;
                }
            }
            if (!temp) {
                return true;
            }
        }
    }
    return false;
}
在讨论区看到另一种判断思路,就是得到重复次数n/m,然后依次重复,再与原字符串比较。这种代码实现比较简单。

具体代码如下:
public boolean repeatedSubstringPattern(String s) {
    int n = s.length();
    for (int i = n / 2; i >= 1; i--) {
        if (n % i == 0) {
            int k = n / i;
            String sub = s.substring(0, i);
            StringBuilder sb = new StringBuilder();
            int j;
            for (j = 1; j < k; j++) {
                if (!sub.equals(s.substring(j * i, i + j * i))) {
                    break;
                }
            }
            if (j == k) {
                return true;
            }
        }
    }
    return false;
}

  1. 有人一做字符串运算,就想到了正则表达式,ok,确实可行。不解释,直接借用别人的代码。
def repeatedSubstringPattern(self, str):
    """
    :type str: str
    :rtype: bool
    """
    import re
    return bool(re.match(r"^([a-z]+)\1+$", str))



作者:如烟花非花
链接:https://www.jianshu.com/p/4406bf26366e
来源:简书
简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。

蛮力法(Brute Force)
时间复杂度 O(k * n),其中n是字符串长度,k是n的约数个数
若字符串可以由其子串重复若干次构成,则子串的起点一定从原串的下标0开始

并且子串的长度一定是原串长度的约数

整数约数的个数可以通过统计其质因子的幂得到,而输入规模10000以内整数的约数个数很少

因此通过蛮力法,枚举子串长度即可
def repeatedSubstringPattern(self, str): """ :type str: str :rtype: bool """ size = len(str) for x in range(1, size / 2 + 1): if size % x: continue if str[:x] * (size / x) == str: return True return False

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts