C++でシーケンスにスタンプを押して目標文字列を作る方法

問題の概要

小文字だけで構成された目標文字列(target)を作りたいと考えます。初期状態では、目標文字列と同じ長さ n の「?」が並んだ列しかなく、これとは別に小文字からなるスタンプ(stamp)が1つ与えられています。

各ターンでは、この列の上にスタンプを重ね、その範囲の文字をスタンプの対応する文字で置き換えることができます。ターン数は最大でも 10 × n 回までです。例えば、初期状態が「?????」でスタンプが「abc」なら、最初のターンで作れるのは「abc??」「?abc?」「??abc」のような文字列です。

列がスタンプの組み合わせで作れる場合は、各ターンでスタンプを押した位置(左端の文字のインデックス)を順に格納した配列を返します。作れない場合は空の配列を返します。たとえば、列が「ababc」でスタンプが「abc」の場合、「?????」→「abc??」→「ababc」と変形できるため、答えは [0, 2] のようになります。

したがって、入力が stamp = "abcd"、target = "abcdbcd" であれば、出力は [3, 0] となります。

解法のアプローチ

この問題は「完成形から逆向きにたどる」ことで解けます。すでに確定した部分を「*」で埋めていき、部分的なスタンプパターンとの一致を探すのがポイントです。手順は次のとおりです。

• 結果を格納する配列 ret を用意する
• ok := true、tsz := 0 で初期化する
• ok が真である限り、以下を繰り返す
  • ok := false、x := 0 とする
  • sz をスタンプの長さから 1 ずつ減らしながらループする
    • i を 0 から(スタンプの長さ − sz)まで増やしながらループする
      • newStamp := 長さ i の「*」列 + スタンプの i 文字目から sz 文字分の部分文字列 + 残りを「*」で埋めた、スタンプと同じ長さのパターンを作る
      • pos := target 内で newStamp が見つかる位置
      • pos が見つかり続ける限り、以下を繰り返す
        • ok := true とし、x に sz を加算する
        • ret の末尾に pos を追加する
        • target の pos から pos + スタンプの長さまでを「*」で埋める
        • pos := target 内で次の newStamp の位置を探す
  • tsz := tsz + x とする
• 配列 ret を逆順に並べ替える
• tsz が target の長さと一致すれば 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<int> movesToStamp(string stamp, string target) {
      vector<int> ret;
      bool ok = true;
      int n = stamp.size();
      int tsz = 0;
      while (ok) {
         ok = false;
         int x = 0;
         for (int sz = stamp.size(); sz > 0; sz--) {
            for (int i = 0; i <= stamp.size() - sz; i++) {
               string newStamp = string(i, '*') +
               stamp.substr(i, sz) + string(stamp.size() - sz - i, '*');
               int pos = target.find(newStamp);
               while (pos != string::npos) {
                  ok = true;
                  x += sz;
                  ret.push_back(pos);
                  fill(target.begin() + pos, target.begin() +
                  pos + stamp.size(), '*');
                  pos = target.find(newStamp);
               }
            }
         }
         tsz += x;
      }
      reverse(ret.begin(), ret.end());
      return tsz == target.size() ? ret : vector<int>();
   }
};
main(){
   Solution ob;
   print_vector(ob.movesToStamp("abcd", "abcdbcd"));
}

入力

"abcd", "abcdbcd"

出力

[3, 0]

まとめ

この手法の核心は、答えとなる手順を前から組み立てるのではなく、完成した文字列側から「どのスタンプが最後に押されたか」を剥がしていく逆算思考です。一致済みの部分を「*」に置き換えていくことで、部分一致の判定が単純な文字列検索だけで完結し、実装も非常にコンパクトになります。最後に「*」に置き換えた文字数の合計(tsz)が target の長さに達しているかを確認すれば、スタンプによる構成が可能だったかどうかも一度に判定できます。