459.|459. 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.)
Solution1：intuitive 思路：
Time Complexity: O(N^2) Space Complexity: O(1)
Solution2：KMP 思路：
https://discuss.leetcode.com/topic/67590/java-o-n
http://www.cnblogs.com/grandyang/p/6087347.html
Time Complexity: O(N) Space Complexity: O(1)
【459.|459. Repeated Substring Pattern】Solution Code：
class Solution {
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;
}}
推荐阅读
- LeetCode（03）Longest|LeetCode（03）Longest Substring Without Repeating Characters
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法
- SPOJ DISUBSTR - Distinct Substrings or SUBST1 - New Distinct Substrings 【不同子串数目】
- SPOJ DISUBSTR - Distinct Substrings 后缀数组，转化
- SP694 DISUBSTR - Distinct Substrings(洛谷 字典树)
- python序列化proto时对repeated修饰数据进行赋值(常用类型和其他类型)
- 注意（字符串substring方法在jkd6,7,8中的差异）
- 467.|467. Unique Substrings in Wraparound String
- LeetCode代码分析——30.|LeetCode代码分析——30. Substring with Concatenation of All Words（理解滑动窗口）
- CodeForces - 914F Substrings in a String