C++で解く「デコード方法 II」― ワイルドカード（*）を含む文字列の復号パターン数を求める

A〜Zの英字からなるメッセージが、次のようなマッピング規則に従って数字へエンコードされていると仮定します。

'A' → 1、'B' → 2、…、'Z' → 26

さらに、エンコードされた文字列には '*' という特殊な文字が含まれることがあります。'*' は 1 から 9 までのいずれかの数字として扱えます。したがって、数字と '*' を含むエンコード済みメッセージが与えられたとき、そのメッセージをデコードできる方法の総数を求めるのがこの問題です。答えが非常に大きな値になる可能性があるため、最終的な結果は 10⁹ + 7 で割った余りを返します。

たとえば入力が "*" だけの場合、考えられるデコード方法は 9 通りあります。これは 1 から 9 までのすべての数字、つまり A から I に対応します。

解法のアプローチ

この問題は動的計画法（DP）を使って効率的に解けます。大まかな流れは以下の通りです。

• 関数 add(a, b) を定義する ― ((a mod m) + (b mod m)) mod m を返す
• 関数 mul(a, b) を定義する ― ((a mod m) × (b mod m)) mod m を返す
• メイン処理では以下を実行する
  • n := 文字列 s の長さ
  • サイズ n + 1 の配列 dp を用意する
  • dp[0] := 1
  • s[0] が '0' の場合は 0 を返す
  • dp[1] := s[0] が '*' なら 9、そうでなければ 1
  • i := 2 から n まで繰り返す
    • first := s[i - 2]、second := s[i - 1]
    • second が '*' の場合 → dp[i] := add(dp[i], mul(9, dp[i - 1]))
    • second が '0' より大きい場合 → dp[i] := dp[i - 1]
    • first が '*' の場合
      • second も '*' の場合 → dp[i] := add(dp[i], mul(15, dp[i - 2]))
      • second が '6' 以下の場合 → dp[i] := add(dp[i], mul(2, dp[i - 2]))
      • それ以外 → dp[i] := add(dp[i], mul(1, dp[i - 2]))
    • first が '1' または '2' の場合
      • second が '*' の場合
        • first が '1' なら → dp[i] := add(dp[i], mul(9, dp[i - 2]))
        • first が '2' なら → dp[i] := add(dp[i], mul(6, dp[i - 2]))
      • (first - '0') × 10 + (second - '0') ≤ 26 の場合 → dp[i] := add(dp[i], dp[i - 2])
  • dp[n] を返す

特に重要なのは '*' 同士が隣接するケースです。「**」は 11〜19（9通り）と 21〜26（6通り）の合計 15 通りの2桁の数として解釈できるため、係数 15 を掛けることになります。

以下の実装例を見ると、より理解が深まるでしょう。

実装例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
    lli add(lli a, lli b){
        return ((a % m) + (b % m)) % m;
    }
    lli mul(lli a, lli b){
        return ((a % m) * (b % m)) % m;
    }
    int numDecodings(string s) {
        int n = s.size();
        vector <int> dp(n + 1);
        dp[0] = 1;
        if(s[0] == '0') return 0;
        dp[1] = s[0] == '*' ? 9 : 1;
        for(int i = 2; i <= n; i++){
            char first = s[i - 2];
            char second = s[i - 1];
            if(second == '*'){
                dp[i] = add(dp[i], mul(9, dp[i - 1]));
            }else if(second > '0'){
                dp[i] = dp[i - 1];
            }
            if(first == '*'){
                if(second == '*'){
                    dp[i] = add(dp[i], mul(15, dp[i - 2]));
                }else if (second <= '6'){
                    dp[i] = add(dp[i], mul(2, dp[i - 2]));
                }else{
                    dp[i] = add(dp[i], mul(1, dp[i - 2]));
                }
            }else if(first == '1' || first == '2'){
                if(second == '*'){
                    if(first == '1'){
                        dp[i] = add(dp[i], mul(9, dp[i - 2]));
                    }else if(first == '2'){
                        dp[i] = add(dp[i], mul(6, dp[i - 2]));
                    }
                }else if((first - '0') * 10 + (second - '0') <= 26){
                    dp[i] = add(dp[i], dp[i - 2]);
                }
            }
        }
        return dp[n];
    }
};
main(){
    Solution ob;
    cout << (ob.numDecodings("2*"));
}

入力

"2*"

出力

15

出力の解説

「2*」の場合、まず各文字を個別にデコードする方法が 2 × 9 = 9 通りあります。さらに「2」と「*」を組み合わせて 21〜26 の2桁の数としてデコードする方法が 6 通りあります。これらを合計すると 15 通りとなり、プログラムの出力と一致します。