p459

发表于 | 分类于 |

LeetCode p459 Repeated Substring Pattern 题解

1.题目：

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.)

题意：

给一个字符串，判断它是否是由某个子字符串积累得到的。

2.解题思路:

从中间往前截取字段，判断是否为基串。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
public class Solution {
    public boolean repeatedSubstringPattern(String str) {
        int a = 1;
		int len = str.length();
		for (int i = len / 2; i > 0; i--) {
			if (len % i == 0) {
				int j = len / i;
				String aString = str.substring(0, i);
				int j2 = 1;
				for (; j2 < j; j2++) {
					// System.out.println((i+"  "+ j2));
					if (!aString.equals(str.substring(i * j2, i * j2 + i)))
						break;
				}
				if (j2 == j)
					return true;
			}
		}
		return false;
    }
}

4.一些总结：