[Leetcode] 792. Number of Matching Subsequences

문제 : https://leetcode.com/problems/number-of-matching-subsequences/

---

 

문자열 s를 탐색하면서 특정 문자들의 인덱스들을 오름차순 배열에 저장해둔다.

(charIndexes = 2차원 배열, charIndexes['a'] = 'a' 문자들의 등장인덱스 리스트)

ex) s="abacb" => charIndexes['a'] = [0, 2], charIndexes['b'] = [1, 4], charIndexes['c']=[3]

 

words 배열의 단어들의 문자를 앞에서부터 탐색하면서 탐색중인 문자가 문자열 s의 subsequences인지 확인해보자.

words를 앞에서부터 탐색하면서 최근에 탐색한 s 인덱스를 index 배열에 저장해둔다.

words[i] = c 인 경우, charIndexes[c] 에서 index보다 큰 가장 작은 인덱스를 찾은 후 index에 갱신한다. 만일 index보다 큰 수가 없다면 words[i]는 subsequence가 될 수 없는 경우이다.

ex) s="abacb", words[i] = "bc"

      -> 'b' : index = -1(초기값), charIndexes['b'] = [1,4] -> index 1로 갱신.

      -> 'c' : index = 1, charIndexes['c'] = [3] -> index 3으로 갱신. 

      -> 모든 문자 탐색완료. 탐색종료 "bc"는 s의 subsequence.

ex) s="abacb", words[i] = "ca"

      -> 'c' : index = -1(초기값), charIndexes['c'] = [3] -> index 3으로 갱신.

      -> 'a' : index = 3, charIndexes['a'] = [0, 2] -> index 3보다 큰 경우가 없기 때문에 탐색종료. "ca"는 s의 subsequence가 될 수 없다.

 

문자열 s의 길이가 가장 크기 때문에 s를 탐색하는 시간을 줄여야 한다.

-> 동일 char 인덱스 배열에서 최근에 탐색한 인덱스보다 큰 것을 찾을 때, 이진탐색으로 구현하여 시간을 줄인다.

 

let, N = s.length, M = words.length, K = words[i].length

이 경우, 시간복잡도는 O(MKlog(N)).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/792.%20Number%20of%20Matching%20Subsequences.cpp