[Leetcode] 1032. Stream of Characters

문제 : https://leetcode.com/problems/stream-of-characters/

---

문자열 리스트 words가 입력으로 주어지고 추가될 알파벳 소문자가 한 글자씩 입력으로 들어온다.

추가될 알파벳들은 초기 빈문자열에서 뒤에 하나씩 추가된다. 알파벳이 하나씩 추가되어 만들어진 문자열의 접미사가 words 배열에 존재하는지 판단해라.

---

트라이(Trie)를 만들어야 한다.

words 문자열들을 뒤에서 부터 탐색하면서 트라이를 만들어간다.

[그림1]

예를 들어, words = ["abc", "bc", "dc"] 인 경우 [그림 1]과 같은 트라이가 만들어진다.

1번 노드가 트라이의 헤드 노드이며 빨간색 체크한 부분이 문자열의 끝을 의미한다.

 

알파벳들을 하나씩 받으며 만들어진 문자열을 마찬가지로 뒤에서부터 탐색하면서 트라이의 헤드 노드부터 타고 내려간다.

탐색하면서 문자열의 끝을 의미하는 노드가 있으면 true를 반환한다. 만약 탐색 중 노드를 더 이상 찾을 수 없거나 탐색이 완료되었는데도 문자열의 끝을 의미하는 노드를 탐색한 적이 없다면 false를 반환한다.

 

N = |words|, M = |words[i]|, Q = |query| 이라 했을 때,

트라이를 만드는데 O(NM), 쿼리들을 수행하는데 O(MQ)가 소요되므로 총 시간복잡도는 O(NM) 이다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/1032.%20Stream%20of%20Characters.cpp