leetcode 459. Repeated Substring Pattern 暴力拆分即可

小鱼儿 2022-06-03 01:36 142阅读 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.)

这道题题意很简单，最长我以为要分析字符的情况，后来发现直接暴力拆分即可，这样更简单，就这么做吧

代码如下：

#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;
        }
    };