[Easy] 459. Repeated Substring Pattern

문제

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

문자열이 주어지면, 그 문자열의 부분 문자열이 원본 문자열을 여러 개로 구성할 수 있는지 판별하여 true, false를 반환하시오.

예시

ample 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.

 

해결 과정

• 우선 s 문자열의 길이가 2보다 작으면 false를 반환한다.
• pattern 문자열을 저장할 변수를 선언한다.
• for문을 순회한다. 이때, s 길이의 절반만 순회한다. 절반 이상을 순회하게 된다면, 그것은 더이상 pattern 문자열이 존재할 수 없기 때문이다. (pattern 문자열은 원본 문자열에 적어도 2번 이상 들어가야 하기 때문이다)
  • pattern 문자열에 s[i] 문자를 추가한다.
  • 이때, s 문자열에서 pattern 문자열을 삭제했을 때 반환되는 문자열이 빈 문자열이면 true를 반환한다. 이는 s 문자열이 pattern 문자열로 구성되어 있다는 뜻이다.
• for문을 순회한 후 빠져나오게 되면 false를 반환한다.

나의 코드는 시간복잡도가 높기 때문에, 더 빠르고 간단하게 풀 수 있는 풀이도 함께 첨부한다.

s 문자열을 두 번 반복한 후 맨 처음 문자와 마지막 문자를 제외한 후 그 안에 s가 존재하는지 판별하는 해결 코드이다.

해결 코드

/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function(s) {    
    if (s.length < 2) return false;
    
    let pattern = '';
    for (let i = 0; i < s.length / 2; i++) {
        pattern += s[i];
        if (!s.replaceAll(pattern, '')) return true;
    }
    
    return false;
};

 

더 빠른 코드

/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function(s) {
    return s.repeat(2).slice(1, -1).includes(s);
};