LeetCode 459 Repeated Substring Pattern

문제 URL : https://leetcode.com/problems/repeated-substring-pattern/

Repeated Substring Pattern - LeetCode

 

문제접근법 : s보다 길이보다 작은 특정길이를 연속적으로 붙여서 s가 만들어지는지 확인하는 문제입니다.

s를 만드는 특정 문자열을 t라할때 t의길이 는 s의길이/2 이하여야 합니다. 그래야 s의길이만큼 정확하게

만들수가 있을겁니다. 그렇지만 t의 길이가 모든지 1부터 s의길이/2 이하까지 모두 포함하진 않습니다. 왜냐하면 

s의길이의 약수가 아닐경우 이어붙어봤자 절대 s를 만들수 없을테니까요 이조건만 만족해서

특정길이가 만들어진다면 특정길이에 매칭되는 개수 cnt는 반드시 cnt=s.size()/t.size()가 될것입니다.

 

이것만 확인한다면  문제는 쉽게 풀립니다.

 

소스코드 :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include <bits/stdc++.h> using namespace std;   class Solution { public:     bool repeatedSubstringPattern(string s) {         for (int len = 1; len <= s.size() / 2; len++) {             if (s.size() % len)continue;             int cnt = 0;             string t = s.substr(0, len);             for (int i = 0; i < s.size(); i += len) {                 if (t == s.substr(i, len))                     cnt++;                 else                     break;             }             if (cnt == s.size() / len)return true;         }         return false;     }   }; Colored by Color Scripter

cs

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.