[C++] LeetCode/Hard/0745-prefix-and-suffix-search

Prefix and Suffix Search (LeetCode 745)

문제 개요

• 문제 설명:
  주어진 문자열 배열 words에서, 특정 접두사(pref)와 접미사(suff)를 모두 만족하는 단어 중 가장 큰 인덱스를 반환하는 문제이다.
• 문제의 어려움:
  단순한 선형 검색이나 해시맵 기반 방법으로는 모든 단어에 대해 접두사와 접미사를 확인해야 하므로 비효율적이다.
  따라서, 빠른 검색을 위해 Trie(트라이) 자료구조를 활용하는 최적화된 방법이 필요하다.

접근 방식: Trie를 이용한 최적화

• 핵심 아이디어:
  한 단어의 모든 가능한 접두사와 접미사 조합을 미리 Trie에 삽입해 놓는다.
  이를 통해 f(pref, suff) 함수 호출 시, suff + "{" + pref 문자열을 만들어 한 번의 탐색으로 원하는 단어의 인덱스를 찾아낼 수 있다.
• 왜 "{"인가?
  '{' 문자는 알파벳 'z'보다 뒤에 오기 때문에, 접미사와 접두사를 구분하는 구분자(separator) 역할을 한다.
  예를 들어, 단어 "apple"의 경우, "apple{" 형태로 만들어 접미사와 접두사의 조합을 관리한다.

코드 동작 원리

1. TrieNode 구조체
   • 각 노드는 unordered_map<char, TrieNode*> children를 가지고 있어 다음 문자를 가리키며,
   • index 멤버는 현재 노드를 거치는 단어들 중 마지막에 나온(즉, 가장 큰 인덱스) 단어의 인덱스를 저장한다.
2. 생성자 WordFilter(vector<string>& words)
   • 각 단어에 대해 word + "{" 형태의 문자열을 만든다.
   • 이 문자열을 이용해 모든 가능한 접미사와 접두사의 조합을 Trie에 삽입한다.
   • 예를 들어, 단어 "apple"이라면,
     • "apple{", "pple{", "ple{", "le{", "e{", "{" 등을 고려하며,
     • 각 삽입 시마다 해당 노드의 index를 현재 단어의 인덱스로 갱신한다.
3. 함수 f(string pref, string suff)
   • 입력받은 접두사와 접미사를 조합해 쿼리 문자열 query = suff + "{" + pref를 생성한다.
   • Trie를 순회하면서 해당 경로가 존재하면, 최종 노드의 index를 반환하고,
   • 경로가 없다면 -1을 반환한다.

코드 전체

class WordFilter {
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        int index = -1;
    };
    
    TrieNode* root;
    
public:
    WordFilter(vector<string>& words) {
        root = new TrieNode();
        int n = words.size();
        
        for (int i = 0; i < n; i++) {
            // '{'는 알파벳보다 큰 값으로, 접두사와 접미사 구분자 역할
            string word = words[i] + "{";  
            int len = word.size();
            
            // 모든 가능한 접미사 + 접두사 조합을 Trie에 삽입
            for (int j = 0; j < len; j++) {
                TrieNode* node = root;
                for (int k = j; k < 2 * len - 1; k++) {
                    char c = word[k % len]; 
                    if (!node->children.count(c)) {
                        node->children[c] = new TrieNode();
                    }
                    node = node->children[c];
                    node->index = i; // 현재 단어의 인덱스 (가장 마지막에 삽입된 단어가 우선)
                }
            }
        }
    }
    
    int f(string pref, string suff) {
        string query = suff + "{" + pref;
        TrieNode* node = root;
        
        for (char c : query) {
            if (!node->children.count(c)) return -1;
            node = node->children[c];
        }
        return node->index;
    }
};