LeetCode 392: 文字列の包含関係判定

文字列 s が文字列 t の部分列であるかを確認する問題では、動的計画法（DP）による状態管理が有効です。

DPテーブルによるアプローチ

配列 match[i][j] を「s の先頭 i 文字と t の先頭 j 文字を比較した際の、一致した文字列の最大長」と定義します。

• s[i-1] == t[j-1] の場合：末尾同士が一致するため、直前の一致長に1を加算します。match[i][j] = match[i-1][j-1] + 1
• s[i-1] != t[j-1] の場合：t の現在位置の文字をスキップして探索を継続します。match[i][j] = match[i][j-1]

最終的な match[s.length()][t.length()] が s の全長と等しければ、完全な部分列として成立します。

class Solution {
public:
    bool isSubsequence(string pattern, string source) {
        int pLen = pattern.length();
        int sLen = source.length();
        vector<vector<int>> memo(pLen + 1, vector<int>(sLen + 1, 0));

        for (int i = 1; i <= pLen; ++i) {
            for (int j = 1; j <= sLen; ++j) {
                if (pattern[i - 1] == source[j - 1]) {
                    memo[i][j] = memo[i - 1][j - 1] + 1;
                } else {
                    memo[i][j] = memo[i][j - 1];
                }
            }
        }
        return memo[pLen][sLen] == pLen;
    }
};

双ポインタによる線形走査

空間計算量を O(1) に抑えるため、2つのインデックスを用いて順方向にマッチングを行います。source を走査し、pattern の現在位置と一致した場合のみ pattern 側のポインタを進めます。

class Solution {
public:
    bool isSubsequence(string sub, string main) {
        int subPtr = 0;
        const int subLimit = sub.length();
        
        for (char c : main) {
            if (subPtr < subLimit && c == sub[subPtr]) {
                ++subPtr;
            }
        }
        return subPtr == subLimit;
    }
};

LeetCode 115: 異なる部分列の組み合わせ数算出

ソース文字列 src からターゲット文字列 pat を部分列として抽出できる総組合せを求めます。組み合わせ数は指数関数的に増加するため、64ビット符号なし整数を使用し、オーバーフローを回避します。

二次元状態遷移の実装

ways[i][j] を「src の先頭 i 文字から pat の先頭 j 文字を構築する経路数」と置きます。

• 文字が一致する場合（src[i-1] == pat[j-1]）：src の末尾を対応させるケース（ways[i-1][j-1]）と、対応させずに過去の経路数を継承するケース（ways[i-1][j]）を合算します。
• 文字が不一致の場合：src の末尾は使用できないため、直前の行の値をそのまま引き継ぎます（ways[i-1][j]）。

初期化では、空のターゲットは任意のソースから「全て削除する」1通りで生成可能であるため ways[i][0] = 1 とします。逆に空ソースから非空ターゲットを生成する経路は存在しないため ways[0][j] = 0 です。

class Solution {
public:
    int numDistinct(string src, string pat) {
        int n = src.size();
        int m = pat.size();
        vector<vector<uint64_t>> dpTable(n + 1, vector<uint64_t>(m + 1, 0));

        for (int i = 0; i <= n; ++i) dpTable[i][0] = 1;

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (src[i - 1] == pat[j - 1]) {
                    dpTable[i][j] = dpTable[i - 1][j - 1] + dpTable[i - 1][j];
                } else {
                    dpTable[i][j] = dpTable[i - 1][j];
                }
            }
        }
        return static_cast<int>(dpTable[n][m]);
    }
};

一次元配列による空間最適化

現在の行の計算が直前の行の値のみを参照するため、配列を1次元に圧縮できます。更新順序を逆走査にすることで、同一ラウンド内の値の上書きによるデータ破壊を防ぎます。

class Solution {
public:
    int numDistinct(string src, string pat) {
        vector<uint64_t> counts(pat.size() + 1, 0);
        counts[0] = 1;

        for (char currentChar : src) {
            for (int idx = pat.size(); idx >= 1; --idx) {
                if (currentChar == pat[idx - 1]) {
                    counts[idx] += counts[idx - 1];
                }
            }
        }
        return static_cast<int>(counts.back());
    }
};

正順で更新処理を行う場合は、計算前の旧値を一時変数に退避させる必要があります。これにより、配列の参照順序を変えずに安全な状態遷移を実現できます。

class Solution {
public:
    int numDistinct(string src, string pat) {
        vector<uint64_t> dp(pat.size() + 1, 0);
        dp[0] = 1;

        for (int i = 0; i < src.size(); ++i) {
            uint64_t oldVal = 1;
            for (int j = 1; j <= pat.size(); ++j) {
                uint64_t currentStored = dp[j];
                if (src[i] == pat[j - 1]) {
                    dp[j] += oldVal;
                }
                oldVal = currentStored;
            }
        }
        return static_cast<int>(dp.back());
    }
};