C++での文字列インターリーブ判定：メモ化再帰による動的計画法の実装

文字列インターリーブとは

3つの文字列 s1、s2、s3 が与えられたとき、s3 が s1 と s2 をインターリーブ(交互に織り交ぜる)することで形成できるかどうかを判定する問題です。

例えば、s1 = "aabcc"、s2 = "dbbca"、s3 = "aadbbcbcac" の場合、s3 は s1 と s2 の各文字を順序を保ちながら交互に組み合わせたものになっているため、結果は true になります。

解法のアプローチ

この問題は、メモ化再帰(トップダウン方式の動的計画法)を用いることで効率的に解けます。i、j、k をそれぞれ s1、s2、s3 の現在位置とし、s3 の末尾から逆にたどりながら、注目している文字が s1 または s2 の末尾と一致するかを確認していきます。

具体的な手順は以下の通りです。

• solve() メソッドを定義します。引数は s1、s2、s3、3次元配列 dp、およびインデックス i、j、k です。

• i = 0 かつ j = 0 かつ k = 0 の場合は true を返します(すべての文字を消費した状態)。

• dp[i][j][k] が -1 以外の場合は、すでに計算済みのためその値を返します。

• ans := false で初期化します。

• i > 0 かつ k >= 0 かつ s1[i] == s3[k] の場合、ans := solve(s1, s2, s3, dp, i - 1, j, k - 1) を実行します。

• j > 0 かつ k >= 0 かつ s2[j] == s3[k] の場合、ans := ans OR solve(s1, s2, s3, dp, i, j - 1, k - 1) を実行します。

• dp[i][j][k] := ans を設定し、その値を返します。

メインメソッド側では以下の処理を行います。

• n := s1 のサイズ、m := s2 のサイズ、o := s3 のサイズを取得します。

• s1、s2、s3 の先頭に空白を1つ追加し、インデックスを1始まりにします。

• (n + 1) × (m + 1) × (o + 1) のサイズを持つ3次元配列を作成し、すべて -1 で初期化します(-1 は「未計算」を表します)。

• solve(s1, s2, s3, dp, n, m, o) の結果を返します。

実装例

以下にC++での実装例を示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool solve(string s1, string s2, string s3, vector < vector < vector <int>>>& dp, int i, int j, int k){
      if(i ==0 && j == 0 && k == 0)return true;
      if(dp[i][j][k] !=-1)return dp[i][j][k];
      bool ans = false;
      if(i > 0 && k >= 0 && s1[i] == s3[k]){
         ans = solve(s1, s2, s3, dp, i - 1, j, k - 1);
      }
      if(j >0 && k >=0 && s2[j] == s3[k]){
         ans |= solve(s1, s2, s3, dp, i, j - 1, k - 1);
      }
      return dp[i][j][k] = ans;
   }
   bool isInterleave(string s1, string s2, string s3) {
      int n = s1.size();
      int m = s2.size();
      int o = s3.size();
      s1 = " " + s1;
      s2 = " " + s2;
      s3 = " " + s3;
      vector < vector < vector <int>>> dp(n + 1, vector < vector <int>>(m + 1, vector <int> (o + 1, -1)));
      return solve(s1, s2, s3, dp, n , m , o );
   }
};
main(){
   Solution ob;
   cout << (ob.isInterleave("aabcc", "dbbca", "aadbbcbcac"));
}

入力

"aabcc", "dbbca", "aadbbcbcac"

出力

1

出力が 1(true)となっており、s3 = "aadbbcbcac" が s1 と s2 のインターリーブによって形成可能であることが確認できます。

計算量について

状態 (i, j, k) の組み合わせ数に比例するため、時間計算量・空間計算量はいずれも O(n × m × o) です。メモ化により同じ状態の再計算を避けられるため、素朴な全探索(指数時間)と比べて大幅に高速化されます。