[슬라이딩윈도우][JavaScript][LeetCode] #567. Permutation in String

#슬라이딩 윈도우  #MEDIUM

Permutation in String - LeetCode

🌷 문제 설명

✏️ LeetCode 연습문제: Permutation in String
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.

🎃 제한 사항
1 <= s1.length, s2.length <= 10^4
s1 and s2 consist of lowercase English letters.

입출력 예

s1	s2	result
"ab"	"eidbaooo"	true
"ab"	"eidboaoo"	false

 

🌷 내 코드

또 까먹고 이해하지 못할 미래의 나를 위한 편지..
😇 문제 풀이의 개요는 이렇습니다.
1. 예외 처리 해주기 (s1.length > s2.length) false
2. s1에 포함된 문자열과 그 s1에 저장된 해당 문자열의 갯수를 Set에 key와 value로 저장
     - s1 = "ab" 이면 a 하나, b 하나이므로 아래처럼 Set에 저장할 수 있음
     - Set(0): { a: 1, b:1 } 

4. 이제 그 Set과 윈도우를 가지고 s2를 탐색 (while문)
4-1-1. 만약 s2에서 윈도우 오른쪽 인덱스의 값이 set에 존재한다면(만약 a 라면) set에서 빼준다: {a:0, b:1}
4-1-2. 만약 s2에서 윈도우 오른쪽 인덱스의 값이 set에 존재하지 않는다면 (만약 i 라면) set에서 빼준다: {a:1, b:1, i: NaN}
4-1-3. 만약 s2에서 윈도우 왼쪽의 인덱스 값이 set에 존재한다면(만약 a 라면) set에서 더해준다 
4-1-4. 만약 s2에서 윈도우 왼쪽의 인덱스 값이 set에 존재하지 않는다면 (만약 i 라면) set에서 더해준다: {a:1, b:1, i: NaN}
❓ 왜냐면 이 존재하는 값은 우리의 윈도우 바깥에 위치하게 될 거니까, 얘가 4-1-1에서 깎아먹은 값을 돌려줘야 하는 것
❓ 즉, 존재하든 안 하든 빼고 더해주는 액션은 똑같은데, 우리에게 유효한 것은 set에 존재하는 값 only

4-2-1. 정답을 판별하기 위해 문자열 길이 변수 `charLength` 를 선언한다. (이 변수가 0이 되면 true 반환)
4-2-2. 만약 s2에서 윈도우 오른쪽 인덱스의 값이 set에 존재하는 경우 변수 `charLength` 에 1을 빼준다.
4-2-3. 만약 s2에서 윈도우 왼쪽 인덱스의 값이 set에 존재하는 경우 변수 `charLength`에 1을 더해준다.

 

//  s1 = "ab", s2 = "eidbaooo"
var checkInclusion = function (s1, s2) {
  // s1이 s2보다 긴 경우 s2에 포함될 경우가 없으므로 false반환
  if (s1.length > s2.length) return false;

  // s1에 있는 알파벳 숫자 카운트(key: 알파벳, value: 개수)해서 집어넣기
  // for문을 지나면 charCount={a: 1, b:1}가 됨 (s1에서의 string 개수)
  let charCount = new Set();
  for (let i = 0; i < s1.length; i++) {
    if (charCount[s1[i]] === undefined) {
      // 처음에는 charCount 비어있을 거니까(undefined)
      charCount[s1[i]] = 0; // 0을 일단 할당해줌
    }
    charCount[s1[i]] += 1;
  }

  // console.log(charCount) // Set(0) { a: 1, b: 1 }

  // Sliding Window
  let left = 0; // 윈도우 왼쪽 끝 인덱스
  let right = 0; // 윈도우 오른쪽 끝 인덱스

  // s1이 몇 자인지 확인할 때 쓰는 변수. s2에서 s1에 해당하는 캐릭터를 만나면 하나씩 지울거임
  // 즉 0이 되면 s1의 문자열들이 s2에서 연속적으로 발견된다는 뜻! (즉, true 반환)
  let charLength = s1.length;

  // s2탐색 시작!
  // 윈도우 오른쪽 인덱스는 s2의 길이보다 작아야 함
  while (right < s2.length) {
    // s2[right]이 chraCount에 key로서 존재할 때
    if (charCount[s2[right]] > 0) {
      charLength--; // 빼주자! 이제 남은 길이만 없애면 true 리턴가능
    }
    charCount[s2[right]]--; // 존재한다면 1 빼주고, 존재하지 않으면 NaN(undefined-1 이므로)
    right++; // 오른쪽 인덱스 오른쪽으로 1 옮겨주기

    // charLength가 0이면 true 반환
    if (charLength === 0) return true;

    // s1.length는 고정된 윈도우(window)의 크기.
    // right-left가 목표한 윈도우의 크기일 때,
    if (right - left === s1.length) {
      // s2[left]가 charCount에 키로서 존재했다면
      // charLength를 하나 올리자
      // 왜냐하면 그 존재하는 'left'는 이제 우리의 윈도우 바깥에 위치하게 될 거니까
      if (charCount[s2[left]] >= 0) {
        charLength++;
      }
      charCount[s2[left]]++; // 키로서 존재하지 않으면 NaN, 존재했다면 1 더해줄 것
      left++; // 왼쪽 인덱스 오른쪽으로 1 옮겨주기
    }
  }
  return false; // 끝까지 찾아도 없으면 false 반환
};

🎥 시각자료(Python Tutor)

동영상 서비스가 종료되어 해당 콘텐츠를 재생할 수 없습니다.

동영상 서비스가 종료되어 해당 콘텐츠를 재생할 수 없습니다.

 

🌷 코멘트

Set을 어떻게 갖고 노는지를 잘 알아야 할 것 같다. 사실 아무리 해도 안풀려서...(ㅎ) 남의 코드를 좀 (많이) 참고했는데, 일단 제시된 대다수의 풀이를 이해하는 것 조차 좀 어려웠다. 그나마 내 눈에 제일 잘 보이는 코드를 하나 뜯어가지고 하나 하나 주석을 써서 제대로 이해하고 넘어가려고 했다.
JavaScript는 Python Tutor 같은거 없나..라고 생각했는데 Python Tutor에 JavaScript도 지원해주더라 😮 짱.. 돌려보고 이해 완! 

 

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!

~대가리 꽃밭인 디지털 노마드가 꿈이예요~

🧚‍♀️ Gyumin Lee

📧 gyumin.q.lee@gmail.com

qminlee723 - Overview