歌詞を検索

Description

[この問題は精度と効率テストで1点ずつ占めています]
友人たちから天才プログラマーと呼ばれるプロが音楽の仕事をしている友人からアドバイスを受け、自分の好きな歌詞の中に特定のキーワードがいくつあるかを知りたいとプログラムを開発した.
キーワードはワイルドカードの「?」アレイ形式の文字列が含まれます.ワイルドカード?文字を表し、任意の文字と一致すると仮定します.例えば「fro?」「frodo」、「front」、「frost」などと組み合わせますが、「frame」、「凍結」とは組み合わせません.
歌詞で使用するすべての単語を含む並べ替え単語と検索するキーワードを含む並べ替えクエリーを与える場合は、solution関数を完了し、各キーワードに対応する単語を順番に並べ替えて返します.

Input

歌詞の制限
wordsの長さ(歌詞単語の個数)は2または100000以下である.
各歌詞単語の長さは1万個以下であり、空の文字列は存在しない.
全歌詞の長さの和は2つの1000000を超えない.
同じ単語が複数回歌詞に表示されると、重複は解消され、wordsは1つしか提供されません.
各歌詞の単語はアルファベット小文字のみで構成され、特殊な文字や数字は含まれていないと仮定します.
検索キーの制限
クエリの長さ(検索キーワードの数)は100000以上です.
各検索キーワードの長さは1または10000を超えず、空の文字列は存在しません.
検索キーワードの合計長さは2つの1000000を超えない.
検索キーワードが重複する場合があります.
各検索キーワードはアルファベット小文字とワイルドカード「?」特殊な文字や数字は含まれていないと仮定します.
検索キーワードはワイルドカード「?」1つ以上含まれています.「?」各検索キーワードの接頭辞または接尾辞の1つのみです.
例えば「??odo」「fro?」"?????"可能なキーワードです.
逆に「frodo」(「?」なし)「fr?do」(「?」が真ん中)「ロ?」(「?」は両側にあります)は不可能なキーワードです.

Example

words: ["frodo", "front", "frost", "frozen", "frame", "kakao"]
queries: ["fro??", "????o", "fr???", "fro???", "pro?"]
result : [3, 2, 4, 1, 0]

Code

#include <bits/stdc++.h>

using namespace std;

struct Trie{
    bool leaf;
    int count;
    Trie* next[26];

    Trie(){
        leaf = false;
        count = 1;
        fill(next, next+26, nullptr);
    }
    ~Trie(){
        for(int i=0; i<26; i++)
            if(next[i]) delete next[i];
    }

    void insert(const char* key ){
        if(*key=='\0'){
            leaf = true;
            return;
        } //base case

        int next_char_idx = *key - 'a';
        if(next[next_char_idx] == nullptr)
            next[next_char_idx] = new Trie();
        else next[next_char_idx]->count++;
        next[next_char_idx]->insert(key+1);
    }

    int find(const char* key){
        int curr = *key - 'a';
        if(*key == '?'){
            int tmp = 0;
            for (int j=0; j<26; j++){
                if(next[j] != nullptr)
                    tmp += next[j]->count;
            }
            return tmp;
        }
        if(next[curr] == nullptr) return 0;
        if(*(key+1) == '?') return next[curr]->count;
        return next[curr]->find(key+1);
    }
};


vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer (queries.size(), 0);

    Trie* trie [100001];
    Trie* r_trie [100001];

    for(string str : words){
        int l = str.length();
        if(!trie[l]) trie[l] = new Trie();
        trie[l]->insert(str.c_str());

        reverse(str.begin(), str.end());
        if(!r_trie[l]) r_trie[l] = new Trie();
        r_trie[l]->insert(str.c_str());
    }
    int i=0;
    for (string query : queries){
        int l = query.length();
        if (query[0] == '?'){
            reverse(query.begin(), query.end());
            if(!r_trie[l]){
                i++;
                continue;
            }
            answer[i++] = r_trie[l]->find(query.c_str());
        }else{
            if(!trie[l]){
                i++;
                continue;
            }
            answer[i++] = trie[l]->find(query.c_str());
        }
    }
    return answer;
}

Thoughts

この問題は2020年のKACAブラインド求人第1ラウンドの第4問で、正解率は34.4%効率:0.8%の応募者の大部分が合格しなかった.
問題を読むことと解釈することはあまり難しくありません.逆に、簡単なことではあるが、どのような形で実現するのか、悩んでいた.
制限事項が表示されると,文字長とクエリ長は最大100000個に達し,queryはすべての単語を1つずつ巡回する単純な反復法を取り出して正確性は得られるが,効率的には時間を超える.△最初は私もそうでした.
この問題を解決する方法はいくつかあるが,文字列を探索する際に非常に効率的なデータ構造Trieを用いることで,この問題を非常に簡単に解決できる.
Trie資料構造の詳細については、近く資料構造を整理するとともに、文章を書く際に含める計画だ.

上図に示すように、プレフィックスから始まるqueryであれば「???o」を考慮するため、2つのtrieを使用しました.
接頭辞から?あるqueryは前からではなく後ろからwordを探せばいいので単語の後ろからのr trieを実現しました.
したがって、クエリー時に「?」接頭辞から始まるかどうかを確認し、接頭辞から始まるか、r trieで単語をクエリーし、接尾辞から始まるか、trieで単語をクエリーすればいい.
このように実現して、私は効率的に合格しませんでした.
したがって、trieが単語をクエリーする前に、単語の長さを事前にチェックすれば時間を短縮できるので、trie配列を作成し、単語の長さに応じてそれぞれ実現することができます.query.length()に一致するtrie[query.length()]で単語を問合せます.
このようにしてもいくつかの効率は通過しません...
前回効率を上げてみた方法は何ですか?これは,出現時に単語を再照会することを防止する方法である.
queryを使用してtrieでクエリーを行う場合、興味のあるqueryのcharは「?」この瞬間,直ちにサブノードに向かう必要がなく,そのノードのcount値を直接返す方法はさらに時間を短縮し,すべての効率テストに合格することができる.
整理すると、
難しい問題ですか.そうではないようです.問題を理解するのに何の障害もない.
ただ「どうするか」は重要な問題です.
このような状況でtrie資料構造を書くには,より多くの経験,特徴,理解度を増やすしかなく,他の方法は不明である.
KACA公式解説ではこちらを探索する方法に言及しており、今後もこの探索を利用した解答に挑戦する.