May LeetCoding Challenge[Day18] - Permutation in String

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Input: s1 = "ab"
s2 = "eidbaooo"

Output: True Explanation: s2 contains one permutation of s1 ("ba").

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 해당 문제는 s1의 짧은 문자열과 s2의 긴 문자열이 있을 때, anagram이 성립되면 true, 그렇지 않으면 flase를 반환 값으로 되돌려주는 문제입니다.

 - 이전의 Find All Anagrams in String이랑 똑같은 문제였습니다.

 - 전에 어렵게 풀어서 인지, 해당 해결법을 그대로 가져와서 풀었습니다.

 

2020/05/21 - [내 맘대로 알고리즘/LeetCode 2020 May] - May LeetCoding Challenge[Day17] - Find All Anagrams in a String

May LeetCoding Challenge[Day17] - Find All Anagrams in a String

 

2. 알고리즘 작성 중, 어려운 점 & 깨달은 점

 

- 해당 알고리즘을 SlidingWindow 라고 부른다는 것을 알게 되었습니다.

 

3. 내가 작성한 알고리즘

 

class Solution {
    //s1 = "ab" s2 = "eidbaooo"
    public boolean checkInclusion(String s1, String s2) {
        if(s1.length() > s2.length()){
            return false;
        }
        String longWord = s2;
        String shortWord = s1;
        
        int[] longMap = new int['z'-'a'+1];
        int[] shortMap = new int['z'-'a'+1];
        
        boolean isEquals = true;
        
        //O(M)
        //짧은 문자열의 길이만큼 탐색을 1번 해줍니다.
        for(int i=0; i < shortWord.length(); i++){
            longMap[longWord.charAt(i)-'a']++; //init longMap
            shortMap[shortWord.charAt(i)-'a']++; //init shortMap
        }
        
        //O(M)
        //Anagram이 성립되는 지 확인합니다.
        for(int i=0;i<shortMap.length; i++){
            if(longMap[i]!=shortMap[i]){
                isEquals = false;
                break;
            }    
        }
        if(isEquals){
            return isEquals;
        }
        //O(N)
        //짧은 문자열까지 탐색을 했으므로, 짧은 문자열 다음부터 긴문자열까지 탐색을 합니다.
        for(int i=shortWord.length(); i < longWord.length(); i++){
            isEquals = true;
            longMap[longWord.charAt(i)-'a']++;
            longMap[longWord.charAt(i-shortWord.length())-'a']--;
            for(int j=0;j<shortMap.length; j++){
                if(longMap[j]!=shortMap[j]){
                    isEquals = false;
                    break;
                }    
            }
            if(isEquals){
                return isEquals;
            }
        }
        return isEquals;
    }
}

 

4. 결과

 

문제 : https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/536/week-3-may-15th-may-21st/3333/

Account Login - LeetCode