개발자 Lim

조건:

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

의역: 문자열 s가 주어질 때 해당 문자열의 일부분(substring)의 반복으로 이루어질 수 있으면 true 아니면 false를 반환해라. (혹은 해당 문자열이 반복되는 패턴으로 구성되어 있으면 true 아니면 false로 해석해도 좋을 것 같다.)

"abab" 는 "ab"의 반복으로 이루어질 수 있으므로 true

"abc"는 "a", "b", "c", "ab", "bc" 의 반복으로는 만들 수 없기 때문에 false

"abcabcabcabc"는 "abc"의 반복으로 만들 수 있기 때문에 true

풀이: 

1. 모든 경우 체크 (브루트 포스)

class Solution {
    // 시간복잡도 O(nlog n) // 공간복잡도 O(1)
    private boolean isSubsequence(String targte, String s){
        StringBuilder tmp = new StringBuilder("");
        // targte을 반복하여 이어붙여서 s와 같다면 true 아니면 false
        for(int i=0;i<s.length()/targte.length();i++){
            tmp.append(targte);
        }
        if(tmp.toString().equals(s)) return true;
        else return false;
    }
    public boolean repeatedSubstringPattern(String s) {
        char sArray[] = s.toCharArray();
        String target = "";
        // ex "abcde" 라면 "a" "ab"순으로 확인
        // 만약 target의 문자열의 길이가 절반을 넘어가면 false 이므로 절반까지만 반복
        for(int i=0;i<sArray.length/2;i++){
            target +=sArray[i];
            if(isSubsequence(target,s))
                return true;
        }
        return false;
    }
}

1-1. 좀더 개선한 버전

class Solution {
	// 시간 복잡도 O(log n) 공간 복잡도 O(1);
    public boolean repeatedSubstringPattern1(String s) {
        int length = s.length();
        String copy = "";
        for(int i=1;i<=s.length()/2;i++){
            if(length%i==0){
                copy = s.substring(0,i);
                copy = copy.repeat(length/i);
                if(copy.equals(s))
                    return true;
            }
        }
        return false;
    }
}

2. indexof() 함수 이용 (만약 일정한 패턴으로 해당 문자열이 이루어져 있다면 중간에 반복되는 패턴이 나올 수 있음을 이용)

class Solution {
	// indexOf() 함수의 시간복잡도는 O(n) 공간 복잡도는 O(1)
    public boolean repeatedSubstringPattern2(String s){
        return (s+s).indexOf(s,1)<s.length();
    }
}

indexof()함수의 시간복잡도에 관한 글: https://stackoverflow.com/questions/70902661/does-indexof-in-js-search-all-the-elements-of-an-array-to-execute 

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