Sliding Window(Permutation String) 문제풀이

Permutation String

문제 설명

• 주어진 문자열 s1, s2가 존재한다.
• s2 문자열에서 s1과 같은 연속된 문자열을 찾으면 true를 반환하고 아니면 false를 반환한다.
• 단, s1 문자열의 순서를 섞어도 s2 문자열 내에 존재하면 존재하는 것으로 간주한다.
• 문자열은 모두 소문자 알파벳이다.

문제 풀이

• 본 문제 풀이는 Sliding Window 라는 알고리즘으로 해결하였는데 전체 소스코드는 다음과 같다.

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        if(len1 > len2) return false;
        
        int[] count = new int[26];
        for(int i = 0; i < s1.length(); i++){
            count[s1.charAt(i) - 'a']++;
        }
        
        for(int i = 0; i < s2.length(); i++){
            count[s2.charAt(i) - 'a']--;
            if(i - len1 >= 0) count[s2.charAt(i - len1) - 'a']++;
            if(allZero(count)) return true;
        }

        return false;
    }
    
    public boolean allZero(int[] count){
        for(int i = 0; i < 26; i++){
            if(count[i] != 0) return false;
        }
        
        return true;
    }
    
}

• s2문자열 안에서 s1과 같은 문자열을 찾는것이 문제의 조건이기 때문에 s1의 길이가 s2보다 크다면 false 이다.

int len1 = s1.length();
int len2 = s2.length();
if(len1 > len2) return false;

• 알파벳 소문자는 총 개수가 26개 이므로 배열을 하나 만든다.
• 그리고 s1 문자열의 각각의 알파벳 개수를 센다.
• 이때, 알파벳은 순서가 있으므로 각각의 인덱스에 개수를 할당한다.

int[] count = new int[26];
for(int i = 0; i < s1.length(); i++){
     count[s1.charAt(i) - 'a']++;
}

• 마지막으로 s2 문자열을 처음부터 비교한다.
• 처음 s1 문자열의 길이만큼은 s2문자열 알파벳의 개수를 뺀다.
• s1 문자열의 길이보다 뺀 알파벳의 개수가 많아지면 앞쪽 알파벳의 개수를 더한다.
• 이를 계속 반복하면서 배열 내의 모든 알파벳의 개수가 0이 된다면 true를 반환하고, s2 문자열의 비교가 끝날때까지 0이 되지 않는다면 false를 반환한다.

for(int i = 0; i < s2.length(); i++){
     count[s2.charAt(i) - 'a']--;
     if(i - len1 >= 0) count[s2.charAt(i - len1) - 'a']++;
     if(allZero(count)) return true;
}

return false;

public boolean allZero(int[] count){
    for(int i = 0; i < 26; i++){
        if(count[i] != 0) return false;
    }
        
    return true;
}

도형 예시

• s1 = "abce", s2 = "fbaec"

1. s2와 비교하기 전 s1의 알파벳 개수 배열 상태

알파벳	a	b	c	d	e	f
개수	1	1	1	0	1	0

2. s2의 첫 문자열 4개를 삽입한 알파벳의 개수

알파벳	a	b	c	d	e	f
개수	0	0	0	0	0	1

3. s2의 두번째 인덱스부터 4개를 삽입한 알파벳의 개수

알파벳	a	b	c	d	e	f
개수	0	0	0	0	0	0

4. 따라서 예시의 정답은 true이다.