leetcode 459. Repeated Substring Pattern 重复子串的确定 + 不需要寻找重复出现的子串 + 暴力拼接即可

向右看齐 2022-05-31 01:39 163阅读 0赞

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

这道题看起来十分麻烦其实十分简单，直接暴力拼接即可

下面是C++的做法，代码如下:

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    class Solution 
    {
    public:
        bool repeatedSubstringPattern(string s) 
        {
            for (int i = s.length() / 2; i >= 1; i--)
            {
                if (s.length() % i == 0)
                {
                    int c = s.length() / i;
                    string tmp = "";
                    for (int j = 0; j < c; j++)
                        tmp += s.substr(0, i);
                    if (tmp == s)
                        return true;
                }
            }
            return false;
        }
    };