C++で解く「ビフォーアフターパズル」：共通する単語でフレーズを結合するアルゴリズム

問題の概要

小文字の英字と半角スペースのみで構成されるフレーズのリストが与えられ、そこから「ビフォーアフターパズル（Before and After Puzzles）」と呼ばれる新しいフレーズを生成することを考えます。各フレーズには先頭・末尾にスペースがなく、連続するスペースも含まれていないものとします。

ビフォーアフターパズルとは、2つのフレーズを結合してできるフレーズのことです。条件は「1つ目のフレーズの最後の単語」と「2つ目のフレーズの最初の単語」が一致することで、この共通単語を介して2つのフレーズをつなぎ合わせます。

求めるのは、リスト内のすべての異なるペア phrases[i] と phrases[j]（i ≠ j）から作れるパズルです。組み合わせる順序にも意味があるため、両方の順序を考慮する必要があります。

最終的な出力は、重複のない文字列のリストとして、辞書順にソートしたものを返します。

入力例と出力例

たとえば、入力が次の場合を考えてみましょう。

["mission statement", "a quick bite to eat", "a chip off the old block", "chocolate bar", "mission impossible", "a man on a mission", "block party", "eat my words", "bar of soap"]

このときの出力は以下の通りです。

["a chip off the old block party", "a man on a mission impossible", "a man on a mission statement", "a quick bite to eat my words", "chocolate bar of soap"]

例えば「a chip off the old block」の末尾の単語「block」と「block party」の先頭の単語「block」が一致するため、「a chip off the old block party」というパズルが生成されます。他の組み合わせも同じ仕組みで作られています。

解法のアプローチ

この問題を効率よく解く鍵は、ハッシュマップを使って「各フレーズの最後の単語」と「その単語を持つフレーズのインデックス」を対応付けておくことです。手順は以下の通りです。

• 結果を格納する文字列配列 ret を定義し、phrases 配列をソートします。

• マップ m を定義し、n を phrases 配列のサイズとします。

• i を 0 ～ n−1 の範囲で繰り返します。

  • s := phrases[i] とし、rspace := 右側から見て最初に現れる空白のインデックス（rfind）を取得します。

  • rspace が見つからなければ s 全体を、見つかれば rspace+1 以降の部分文字列（＝最後の単語）をキーとして、m にインデックス i を登録します。

• 再び i を 0 ～ n−1 の範囲で繰り返します。

  • s := phrases[i] とし、lspace := 左側から見て最初に現れる空白のインデックス（find）を取得します。

  • x := lspace が見つからなければ s 全体、見つかれば先頭から lspace までの部分文字列（＝最初の単語）とします。

  • m にキー x が存在する場合、v := m[x] を取り出し、j を 0 ～ v のサイズまで繰り返します。v[j] が i と異なるなら、phrases[v[j]] と s の x.size() 以降の部分文字列を連結した文字列を ret に追加します。

• ret をソートし、重複する要素を削除して返します。

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    vector<string> beforeAndAfterPuzzles(vector<string>& phrases) {
       vector <string> ret;
       sort(phrases.begin(), phrases.end());
       unordered_map <string, vector <int> > m;
       int n = phrases.size();
       for(int i = 0; i < n; i++){
          string s = phrases[i];
          auto rspace = s.rfind(' ');
          m[rspace == string::npos ? s : s.substr(rspace + 1)].push_back(i);
       }
       for(int i = 0; i < n; i++){
          string s = phrases[i];
          auto lspace = s.find(' ');
          string x = (lspace == string::npos? s : s.substr(0, lspace));
          if(m.count(x)){
             vector <int>& v = m[x];
             for(int j = 0; j < v.size(); j++){
                if(v[j] != i){
                   ret.push_back(phrases[v[j]] + s.substr(x.size()));
                }
             }
          }
       }
       sort(ret.begin(), ret.end());
       ret.erase(unique(ret.begin(), ret.end()), ret.end());
       return ret;
    }
};
main(){
    vector<string> v = {"mission statement","a quick bite to eat","a chip off the old block","chocolate bar","mission impossible","a man on a mission","block party","eat my words","bar of soap"};
    Solution ob;
    print_vector(ob.beforeAndAfterPuzzles(v));
}

入力

["mission statement","a quick bite to eat","a chip off the old block","chocolate bar","mission impossible","a man on a mission","block party","eat my words","bar of soap"]

出力

[a chip off the old block party, a man on a mission impossible, a man on a mission statement, a quick bite to eat my words, chocolate bar of soap]

まとめ

このアルゴリズムでは、各フレーズの末尾の単語をあらかじめマップに索引化しておくことで、先頭の単語との照合を高速に行えます。すべてのペアを総当たりで比較する O(n²) の素朴な手法に比べ、無駄な比較を大幅に減らせる点が大きなメリットです。最後にソートと重複除去を行うことで、仕様どおりの辞書順・ユニークな結果リストが得られます。