Repeated Substring Pattern[E,String,String Matching]

https://leetcode.com/problems/repeated-substring-pattern/description/

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

 

Example 1:

Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.

Example 2:

Input: s = "aba"
Output: false

Example 3:

Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" four times or the substring "abcabc" twice.

 

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters.

1. C

사부작 사부작 조건을 추가해가며 수정했는데, test case의 정오답을 미리 알 수 있었기에 수정할 수 있었다.

test case 가 hide 되어 있었다면 pass가 어려웠을 걸로 예상.

bool repeatedSubstringPattern(char* s) {
    int n = strlen(s);
    for(int i=1;i<=n/2;i++){
        int idx = 0;
        if(n%i==0){
            while(idx+i < n){
                if(s[idx]==s[idx+i]){
                    idx++;
                }else break;
            }
            if(idx+i == n) return true;
        }
    }
    return false;
}

 

2. C++

C와 결은 비슷하게 풀었다.

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        for(int i=1;i<=n/2;i++){
            if(n % i==0){
                int j = 0;
                while(j < n-i ){
                    if(s[j]!=s[j+i]){
                        break;
                    }else j++;
                }
                if(j==n-i) return true;
            }
        }
        return false;
    }
};

 

3. Python

좀 다른 방식으로 접근, 사실 이해는 안 가는데 모범답안 중에 있던 case다.

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        s2 = s*2
        s3 = s2[1:-1]
        return s in s3