[leetcode][567] Permutation in String

문제: https://leetcode.com/problems/permutation-in-string/

---

문자열 s1, s2가 주어졌을 때, s2 서브 문자열에서 s1 문자열 문자들이 전부 존재하는지 구하는 문제.

예를 들어, s1="ab", s2="eidbaooo" 라면 true. s1="ab", s2="eidboaoo" 라면 false.

 

투포인터로 풀었다.

문자열 s1을 전부 탐색하면서 문자개수를 저장한다. (let, arr)

s2 서브 문자열 범위의 시작 위치와 종료 위치를 변수 s, e에 저장한다.

s2 문자열을 탐색하면서 탐색 중인 문자 위치를 e라 하자. (let, nowChar = s2[e])

 

만약 arr[nowChar] 이 0 보다 크다면 arr[nowChar]를 1 감소시키고 다음 문자를 탐색한다.

arr[nowChar] 이 0이하라면 s~e 범위로는 정답을 만들 수 없다는 뜻이므로 nowChar이 나올 때 까지 s를 증가시키면서 arr 배열을 다시 원복한다. 

예를들어, s1="aabb", s2="baaab" 라면, s2 3인덱스를 탐색시 s=0, e=3가 된다. 이 범위내에는 a가 총3개 있는데 s1 문자열에는 a가 2개 있으므로 시작인덱스 s를 다시 재정비시켜야한다. a가 1개 부족한 경우이므로 부족한 a를 찾을때까지 arr[s]를 다시 1씩 추가시키면서 s를 증가시킨다.

s = 0, s2[0] = 'b' : 'b'는 'a'가 아니므로 arr['b']를 1개 추가시키고 s++.

s = 1, s2[1] = 'a' : 'a'를 보충가능하므로 arr['a']를 1개 추가시키고 s++. 후 종료. 

'a'를 하나 보충했으므로 e를 범위에 포함시킬 수 있고, s=2, e=3 이 된다.

 

탐색 중, e-s 가 s1문자열 길이 -1 과 같다면 true, s2문자열을 모두 탐색할때까지 true인 경우가 없다면 false를 반환한다.

 

시간복잡도는 N = |s1|, M = |s2|라 한다면 O(N+M).

---

소스코드

C++ : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/567.%20Permutation%20in%20String.cpp

Python : https://github.com/fpdjsns/Algorithm-python/blob/main/leetcode/medium/567.%20Permutation%20in%20String.py