[LeetCode] 567. Permutation in String - 문제풀이

Description

s2에 s1의 가능한 permutation(순열)이 존재하는지 여부를 반환해주세요. Example1을 예로 들면 s1인 ab로 가능한 순열 ab,ba중 s2 "ba"가 존재하므로 true입니다.

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints:

• 1 <= s1.length, s2.length <= 104
• s1 and s2 consist of lowercase English letters.

Solution 1. Sort이용

public boolean checkInclusion(String s1, String s2) {

		int len1= s1.length();
    int len2= s2.length();
    s1 = sort(s1);
    for (int i = 0; i <= len2-len1; i++) {
        if (s1.equals(sort(s2.substring(i, i+len1)))) // 시작점부터 기준문자(s1)의 길이까지 잘라서 정렬한 뒤 비교
            return true;
    }
    return false;        
}

public String sort(String s) {
		char[] t = s.toCharArray();
    Arrays.sort(t);
    return new String(t);
}

s2의 문자열을 s1의 길이만큼 잘라서 s1,s2의 문자열을 정렬하여 일치 한다면 s1은 s2에 포함되는 수열을 가지게 되므로 true를 반환하고 아니면 다음 글자로 넘어가서 다시 정렬 후 비교합니다. 각각 모든 순열의 경우의 수를 계산하지 않고 각각을 정렬하여 비교하여 쉽게 찾아내지만 정렬에 들어가는 비용때문에 Time Limit Exceeded 발생합니다.

Solution 2. Sliding Window

public boolean checkInclusion(String s1, String s2) {
		//2. Sliding Window
    int len1= s1.length();
    int len2= s2.length();
    if(len1 > len2) return false;
    int[] map = new int[26]; // 소문자 a-z

    for (int i = 0; i < len1; i++) { // save s1 Count
        map[s1.charAt(i)-'a']++;
    }

    for (int i = 0; i < len2; i++) { // count 0이되는 케이스 슬라이딩윈도우로 진행하며 체크
        map[s2.charAt(i)-'a']--;
        if(i-len1 >= 0){ map[s2.charAt(i-len1)-'a']++;} //기준글자 이상 넘어갔을경우 이전 윈도우 왼쪽의 이전 글자는 ++해줌.
        if(allZero(map)){
           return true;
        }
    }
    return false;        
}

두 문자열에 동일한 문자가 동일한 횟수만큼 포함된 경우에 순서와 관계없이 순열을 포함하는 것을 메인 아이디어로 합니다. 알파벳 소문자 기준 count를 기록할 int[26] 배열을 만들어 준 뒤 기준이 되는 s1의 알파벳별 count를 기록합니다.

이후 비교대상인 s2의 문자열을 배열의 모든 알파벳의 count가 0이 될 때까지 슬라이딩 윈도우로 체크해 가며 0이되는 케이스가 있다면 true, 모두 스캔했는데 0이 아니라면 일치하는게 없는 것으로 false를 반환합니다.

Reference

Permutation in String - LeetCode