本文主要是介绍LeetCode-Repeated_Substring_Pattern,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:
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: TrueExplanation: It's the substring "ab" twice.
Example 2:
Input: "aba"Output: False
Example 3:
Input: "abcabcabcabc"Output: TrueExplanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)
翻译:
给定一个非空的字符串判断它是否可以由它的一个子串复制多次拼接构成。你可以假设给定的字符串值包含小写的英文字母并且它的长度不超过10000。
例子1:
输入: "abab"输出: True解释: 它是两次子串"ab"
例子2:
输入: "aba"输出: False
例子3:
输入: "abcabcabcabc"输出: True解释: 它是四次子串"abc"。(两次子串"abcabc")
思路:
子串的长度sub.size()一定小于等于整个字符串长度s.size()的一半,因此,先找到一个子串,然后将它拼接 s.size()/sub.size() 次,构成字符串 t,比较 t 和 s ,若相等,则返回true;否则,返回false。
C++代码(Visual Studio 2017):
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;class Solution {
public:bool repeatedSubstringPattern(string s) {int n = s.size();for (int i = n / 2; i >= 1; i--) {if (n % i == 0) {int c = n / i;string t = "";for (int j = 0; j < c; j++) {t += s.substr(0, i);}if (t == s)return true;}}return false;}
};int main()
{Solution s;string str = "abcabcabcabc";bool result;result = s.repeatedSubstringPattern(str);cout << result;return 0;
}
这篇关于LeetCode-Repeated_Substring_Pattern的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!