C++で文字を削除して作れる辞書内の最長単語を求める方法

問題の概要

文字列 s と文字列のリスト（辞書）d が与えられます。このとき、与えられた文字列 s からいくつかの文字を削除することで作れる、辞書の中で最も長い単語を見つけます。候補が複数存在する場合は、最も長く、かつ辞書順（レキシコグラフィカル順）で最小の単語を返します。条件を満たす単語が存在しない場合は、空文字列を返します。

たとえば、入力が s = "abpcplea"、d = ["ale", "apple", "monkey", "plea"] の場合、"abpcplea" から不要な文字を削除して "apple" を作ることができるため、答えは "apple" になります。

ポイント：部分列の判定

「文字を削除して作れる」という条件は、その単語が元の文字列の部分列（subsequence）になっていることを意味します。部分列とは、文字の並び順を保ったまま一部の文字を抜き出して得られる列のことです。したがって、辞書内の各単語について「それが s の部分列かどうか」を判定し、条件を満たすものの中から最長・辞書順最小の単語を選べばよいことになります。

アルゴリズムの手順

この問題は、次の手順で解くことができます。

• isSubsequence() メソッドを定義します。引数として s1（元の文字列）と s2（判定対象の単語）を受け取ります。
• ポインタ j を 0 で初期化します。
• i を 0 から s1 のサイズ - 1 までループします。
  • s2[j] が s1[i] と一致したら、j を 1 増やします。
  • j が s2 のサイズに達したら、ループを中断します。
• ループ終了後、j が s2 のサイズと等しければ true を返します（s2 が s1 の部分列であることを意味します）。
• メインの findLongestWord() メソッドでは、次のように処理します。
  • ans を空文字列で初期化します。
  • i を 0 から d のサイズ - 1 までループし、x = d[i] とします。
  • x の長さが ans より長い、または長さが同じで x が ans より辞書順で小さい場合に限り、isSubsequence(s, x) を呼び出します。
  • isSubsequence(s, x) が true を返せば、ans を x で更新します。
• 最後に ans を返します。

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

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool isSubsequence(string s1, string s2){
       int j = 0;
       for(int i = 0; i < s1.size(); i++){
          if(s2[j] == s1[i]){
             j++;
             if(j == s2.size()) break;
          }
       }
       return j == s2.size();
    }
    string findLongestWord(string s, vector<string>& d) {
       string ans = "";
       for(int i = 0; i < d.size(); i++){
          string x = d[i];
          if(x.size() > ans.size() || (x.size() == ans.size() && (x < ans))){
             if(isSubsequence(s, x)) ans = x;
          }
       }
       return ans;
    }
};
main(){
    vector<string> v = {"ale","apple","monkey","plea"};
    Solution ob;
    cout << (ob.findLongestWord("abpcplea", v));
}

入力

"abpcplea"
["ale","apple","monkey","plea"]

出力

apple

計算量について

辞書内の各単語に対して部分列判定を行うため、1 回の判定にかかる時間は O(|s| + |word|) です。したがって、全体の時間計算量は O(D × (|s| + L)) となります（D は辞書の単語数、L は単語の最大長）。また、答えを保持する文字列以外に余分な領域を使用しないため、空間計算量はほぼ O(1) と効率的です。