C++でエンコードされたメッセージをデコードする方法の数を求めるプログラム

問題の概要

エンコードされたメッセージとして、整数の数字からなる文字列が与えられたとします。これらの数字は、アルファベットの特定の文字にマッピングされます。具体的には、a は 1、b は 2、c は 3 というように対応しています。

さらに、メッセージにはワイルドカードとして文字「*」が含まれることがあり、これは 1 から 9 までの任意の数字にマッピングできるとします。メッセージ input が与えられたとき、そのメッセージをデコードできる方法が何通りあるかを求めるのがこの問題です。

具体例

例えば、入力が input = "18" の場合、出力は 2 になります。

このメッセージは「ah」とデコードできます。1 が「a」に、8 が「h」に対応するためです。また、18 という 2 桁の数は「r」に対応するため、「r」とデコードすることもできます。したがって、この入力をデコードする方法は合計 2 通りあります。

解法のアプローチ

この問題は動的計画法(DP)を使うことで効率的に解けます。各位置 i までの部分文字列をデコードする方法の数を配列に記録しながら、1 桁の数字として読む場合と 2 桁の数字として読む場合の組み合わせを順に累積していきます。ワイルドカード「*」が現れた場合は、取りうる値(1〜9)の数に応じて場合分けして計算します。

アルゴリズムの手順

• n := 入力文字列の長さとする
• サイズ n+1 の配列 dynArr を定義し、すべて 0 で初期化する
• p := 1、k := '0'、dynArr[0] := 1 とする
• i = 1 から n まで、i を 1 ずつ増やしながら以下を繰り返す
  • c := input[i - 1] とする
  • c が 0 であり、かつ k が '1'、'2'、'*' のいずれでもない場合は、デコード不可能なため p := 0 としてループを抜ける
  • input[i - 1] が '*' の場合
    • dynArr[i] := (dynArr[i - 1] * 9) mod m(単独で 1〜9 のいずれにもなり得るため)
    • k が '1' または '*' の場合、dynArr[i] := (dynArr[i] + dynArr[i - 2] * 9) mod m
    • k が '2' または '*' の場合、dynArr[i] := (dynArr[i] + (dynArr[i - 2] * 6) mod m) mod m
  • それ以外の場合
    • c が '0' でなければ、dynArr[i] := dynArr[i - 1]
    • k が '1' または '*' の場合、dynArr[i] := (dynArr[i] + dynArr[i - 2]) mod m
    • (k が '2' または '*')かつ input[i - 1] <= '6' の場合、dynArr[i] := (dynArr[i] + (dynArr[i - 2]) mod m) mod m
  • k := c と更新する
• p が 0 でなければ dynArr[n] を返し、そうでなければ 0 を返す

なお、m = 10^9 + 7 は、答えが非常に大きくなるのを防ぐための剰余(モジュロ)です。

実装例(C++)

それでは、上記のアルゴリズムを C++ で実装した例を見てみましょう。

#include<bits/stdc++.h>

using namespace std;

const long m = 1e9 + 7;

int solve(string input) {
    int n = input.length();
    long long dynArr[n + 1] = {0};

    bool p = 1;
    char k = '0';

    dynArr[0] = 1;
    for (int i = 1; i <= n; i++) {
        char c = input[i - 1];
        if (c == 0 && !(k == '1' || k == '2' || k == '*')) {
            p = 0;
            break;
        }
        if (input[i - 1] == '*') {
            dynArr[i] = (dynArr[i - 1] * 9) % m;
            if (k == '1' || k == '*') dynArr[i] = (dynArr[i] + dynArr[i - 2] * 9) % m;
            if (k == '2' || k == '*') dynArr[i] = (dynArr[i] + (dynArr[i - 2] * 6) % m) % m;
        } else {
            if (c != '0') dynArr[i] = dynArr[i - 1];
            if (k == '1' || k == '*') dynArr[i] = (dynArr[i] + dynArr[i - 2]) % m;
            if ((k == '2' || k == '*') && input[i - 1] <= '6') dynArr[i] = (dynArr[i] + (dynArr[i - 2]) % m) % m;
        }
        k = c;
    }
    return p ? dynArr[n] : 0;
}

int main() {
   cout<< solve("18") <<endl;
   return 0;
}

入力

18

出力

2

まとめ

このプログラムでは、動的計画法を用いて、数字列とワイルドカード「*」を含むエンコード済みメッセージをデコードできるパターンの総数を O(n) の計算量で求めています。各桁を単独で読むか、直前の桁と合わせて 2 桁で読むかを場合分けすることで、「18」のような入力に対して正しく 2 通りという答えが得られます。デコード不可能な並び(例えば先行する '0' など)が検出された場合は 0 を返すようになっています。