首页 > 代码库 > LeetCode 459 Repeated Substring Pattern

LeetCode 459 Repeated Substring Pattern

2024-08-29 16:37:43   215人阅读

Problem:

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

Analysis:

判断所给的字符串是否为某字符串重复两次或多次。

Summary:

1. 暴力法：首先通过所给字符串长度枚举出可以作为重复子串的字符串长度，在每个枚举中，分别判断是否满足题意。

 1 bool repeatedSubstringPattern(string str) {
 2         int len = str.size();
 3         for (int i = 1; i <= len / 2; i++) {
 4             if (len % i == 0) {
 5                 string sub = str.substr(0, i);
 6                 
 7                 int j;
 8                 for (j = 1; j < len / i; j++) {
 9                     if (sub != str.substr(i * j, i)) {
10                         break;
11                     }
12                 }
13                 
14                 if (j == len / i)
15                     return true;
16             }
17         }
18         
19         return false;
20     }

2. 简便运算：将两个所给字符串s1首尾相连组成新的字符串s2 = s1 + s1，将s2首位字符去掉变为字符串s3。

若s1为满足题意的字符串，s3中必存在s1。

参考：https://discuss.leetcode.com/topic/68206/easy-python-solution-with-explaination

 1 class Solution {
 2 public:
 3     bool repeatedSubstringPattern(string str) {
 4         int len = str.size();
 5         string newStr = str + str;
 6         newStr = newStr.substr(1, 2 * len - 2);
 7         
 8         return newStr.find(str) != -1;
 9     }
10 };

 

LeetCode 459 Repeated Substring Pattern


联系
我们