C++で実装する検索候補システム：入力文字に応じた商品名サジェスト機能の作り方

問題の概要

商品名の文字列配列 products と、検索語 searchWord が与えられたとします。ここで、searchWord の各文字がタイプされるたびに、products の中から共通の接頭辞（プレフィックス）を持つ商品名を最大3つ提案するモジュールを設計することを目標とします。

候補となる商品が3つより多い場合は、辞書順で最小の3つを返す必要があります。つまり、検索語の各文字が入力されるたびに、その時点での推奨商品リストを求めるのがこの課題です。

入力例と出力例

例えば、入力が次のようになっている場合を考えます。

• products = ["mobile", "mouse", "moneypot", "monitor", "mousepad"]
• searchWord = "mouse"

このとき、出力は以下のようになります。

[["mobile","moneypot","monitor"],
 ["mobile","moneypot","monitor"],
 ["mouse","mousepad"],
 ["mouse","mousepad"],
 ["mouse","mousepad"]]

「m」や「mo」の段階では mobile・moneypot・monitor が該当し、「mou」以降は mouse・mousepad だけがマッチするため、このような結果になります。

解法のアプローチ

この問題は、ソート済みの商品リストを接頭辞ごとに事前登録しておくことで、効率よく解くことができます。手順は以下の通りです。

• キーが文字列型、値が文字列リスト型のマップ m を定義する。

• 商品配列 p をあらかじめソートしておく。これにより、マップに登録された順序が自動的に辞書順になる。

• i を 0 から p のサイズ − 1 まで繰り返す。

  • x := 空文字列

  • j を 0 から p[i] の長さ − 1 まで繰り返す。

    • x := x + p[i][j]（1文字ずつ接頭辞を伸ばしていく）

    • m[x] の要素数が3未満であれば、p[i] を m[x] のリストに追加する。

• 結果格納用の文字列の二次元配列 res を作成し、temp := 空文字列とする。

• i を 0 から s のサイズ − 1 まで繰り返す。

  • temp := temp + s[i]（検索語を1文字ずつ伸ばす）

  • res に m[temp] を追加する。

• res を返す。

ポイントは、商品配列を先にソートしておくことで、各接頭辞に対して「辞書順で最小の3件」だけを自然に保持できる点です。これにより、検索時にはマップを参照するだけで即座に答えを取得できます。

C++による実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << "[";
       for(int j = 0; j <v[i].size(); j++){
          cout << v[i][j] << ", ";
       }
    cout << "],";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    vector<vector<string>> suggestedProducts(vector<string>& p,
    string s) {
       map <string, vector < string > > m;
       sort(p.begin(), p.end());
       for(int i = 0; i < p.size(); i++){
          string x = "";
          for(int j = 0; j < p[i].size(); j++){
             x += p[i][j];
             if(m[x].size()<3)m[x].push_back(p[i]);
          }
       }
       vector < vector <string> > res;
       string temp = "";
       for(int i = 0; i < s.size(); i++){
          temp += s[i];
          res.push_back(m[temp]);
       }
       return res;
    }
};
main(){
    vector<string> v =
    {"mobile","mouse","moneypot","monitor","mousepad"};
    Solution ob;
    print_vector(ob.suggestedProducts(v, "mouse"));
}

入力

["mobile","mouse","moneypot","monitor","mousepad"]
"mouse"

出力

[[mobile, moneypot, monitor],[mobile, moneypot, monitor],[mouse,
mousepad],[mouse, mousepad],[mouse, mousepad]]

まとめ

この手法では、すべての商品名の全接頭辞をマップに事前登録するため、計算量は商品数 N、平均的な商品名の長さ L として O(N × L) の前処理と、検索語長 M に対して O(M) の参照で済みます。ECサイトの検索窓などでよく見られる「入力補完（オートコンプリート）」機能の基本的な仕組みであり、Trie（トライ木）を使った実装と並んで、サジェスト機能の代表的な解法の一つです。