Repeated Substring Pattern

发表于 | 分类于

Repeated Substring Pattern

题目描述：

给定一个字符串，要求判断这个字符串能否由其子串的整数倍连接而成。

例子：

具体描述见LeetCode459

解题思路：

根据题意我们可以知道子串的长度最少是1，最大是字符串的1/2。所以我们从1开始遍历到总长度的1/2；然后判断每个长度是否是符合条件即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        
        for (int i = 1; i <= s.size() / 2; i++){
            if (check(s.substr(0, i), s))
                return true;//取出开头的前i个字符作为pattern来判断
        }
        return false;
    }
    bool check(string pattern, string target){
        int size = pattern.size();
        int cur = 0;
        while(cur < target.size()){
            if (target.substr(cur, size) != pattern)
                return false;
            else
                cur = cur + size;
        }
        return true;
    }
};