[leetcode] 1160. Find Words That Can Be Formed by Characters

문제 : https://leetcode.com/problems/find-words-that-can-be-formed-by-characters/

---

Map을 이용.

일단 chars 문자열을 모두 방문하면서 { 문자, 개수 }를 map에 저장한다.

words 문자열들을 방문하면서 현재 탐색 중인 문자열의 문자도 탐색한다.

탐색 중인 문자가 chars map에 있는지 확인하고 있는 경우 개수를 1개 빼준다. 만약 문자가 map에 없거나 map에 탐색중인 문자의 개수가 0개라면 good string이 아니므로 탐색을 종료한다.

good string이 될 수 있는 경우(탐색중인 문자열의 모든 문자들을 탐색완료 시) 문자열의 문자 길이를 정답에 더해준다.

 

N : strings의 개수 / M : strings[i]의 길이 / K : chars 문자열의 길이

라고 했을 때 시간복잡도는 O(NM * logK)이다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1160.%20Find%20Words%20That%20Can%20Be%20Formed%20by%20Characters.cpp