23.08.21. 풀었던 문제들 복기

Leetcode 459. Repeated Substring Pattern, 15분

 주어진 대로 구현만 하면 되는 문제.

 일단 substring으로 원 string을 표시하기 위해서는 substring의 길이가 s의 약수여야 한다. 만약 그렇다면, 해당 substring을 q개(s.length()/substr.length())만큼 만들어서 전체를 살펴보면 된다.

// Runtime 19 ms Beats 64.17%
// Memory 15.4 MB Beats 38.41%

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int len = s.length();
        for(int i = 0; i<len/2; i++){
            if(len % (i+1) == 0){
                string substr = s.substr(0, i+1);
                bool repeated = true;
                for(int q = 1; q<len/(i+1); q++){
                    if(s.substr(q*(i+1), i+1) != substr) {
                        repeated = false;
                        break;
                    }
                }
                if(repeated) return true;
            }
        }
        return false;
    }
};