LeetCode 392: Is Subsequence - 今日も窓辺でプログラム

この記事で扱う問題

LeetCodeの392 Is Subsequenceという問題を解きます。

文字列 s と t があるとき、sがtの部分列 (subsequene)かどうかを判定せよ。
sとtは英語の小文字のみを含む文字列で、tは長い(50万文字）こともあるが、sは短い文字列(100文字以下)であると仮定してよい。
例1：
s = "abc", t = "ahbgdc"
結果→true
例2:
s = "axc", t = "ahbgdc"
結果→false.
https://leetcode.com/problems/is-subsequence/

LeetCode自体の解説記事はこちら：
LeetCode: コーディング面接に向けた練習に使えるサイトの紹介 - 今日も窓辺でプログラム

部分列といったら動的計画法？

最長共通部分列を扱う場合は動的計画法、と刷り込まれているので、この問題もまずは動的計画法で書いてみました。bool値の|s| x |t|次元のテーブルdp[i][j]をもっておき、 $s_{[0, i)}$ が $t_{[0, j)}$ の部分列になっている場合 dp[i][j] = true となるように値を埋めていきます。( $s_{[0, i)}$ はsの0文字からi-1文字目までの部分文字列)

class Solution1 {
public:
    bool isSubsequence(string s, string t) {
        if (s.size() == 0) { return true; }
        if (t.size() == 0) { return false; }

        vector<vector<bool>> dp(s.size(), vector<bool>(t.size(), false));
        dp[0][0] = (s[0] == t[0]);
        for (size_t j = 1; j < t.size(); j++) {
            dp[0][j] = (dp[0][j - 1] || (s[0] == t[j]));
        }

        if (!dp[0][t.size() - 1]) { return false; } // 早期切り上げ

        for (size_t i = 1; i < s.size(); i++) {
            for(size_t j = 1; j < t.size(); j++) {
                // dp[i][i] は 次のどちらかが満たされたら true となる
                // (1) dp[i][j-1] == true。つまりs.substr(0, i)が既にt.substr(0, j-1)の部分列ならt.substr(0, j)の部分列でもある。
                // (2) (dp[i-1][j-1] == true) && (s[i] == t[j])。s[i]とt[j]の前までが部分列になっていて、s[i]とt[j]が同じ文字の場合もOK。
                dp[i][j] = (dp[i][j-1] || (dp[i-1][j-1] && (s[i] == t[j])));
            }

            if (!dp[i][t.size() - 1]) { return false; } // 早期切り上げ
        }

        return dp[s.size() - 1][t.size() -1];
    }
};

計算量は、時間空間ともに $O(|s| \cdot |t|)$ です。アルゴリズム自体は正しいと思うのですが、このコードを提出しても制限時間超過で受け付けてもらえません。
コード中の // 早期切り上げというコメントがある箇所で、sがtの部分文字列でないと早々にわかった場合は早めにfalseを返すコードを入れて少しでも実行時間を短くしようとしてみましたが、それでもだめでした。

Two Pointers

実はsがtの部分列かどうかを判定するだけなら、動的計画法を使用する必要はありません。
sとtの文字列を先頭から順に操作するポインタiとjを定義しておき、同じ文字が現れる箇所をチェックしながらポインタを進めていけばOKです。
例えば最初はi = j = 0からスタートですが、文字s[0]が文字列tに出現するかどうかチェックします。出現するならその位置までjを進め、最後までs[0]が出現しなければsはtの部分列ではありません。これを、iも0から順に増やして最後まで回します。
説明下手なので、さっそくコードを見てください。

class Solution2 {
public:
    bool isSubsequence(string s, string t) {
        // check
        if (s.size() == 0) { return true; }
        if (t.size() == 0) { return false; }

        size_t j = 0;
        for (size_t i = 0; i < s.size(); i++) {
            // s[i]がt[j]以降に出現するかどうかチェック
            // s[i] == t[j] となるまでjをインクリメント
            while ((j < t.size()) && (s[i] != t[j])) { j++; }

            // もしtを最後まで走査してもs[i]を見つけられなかったら、sはtの部分列ではない
            if (j >= t.size()) { return false; }

            // jを1つ進めて、次のs[i]に移る
            j++;
        }

        return true;
    }
};

これだと、時間計算量 $O(|s| + |t|)$ , 空間計算量O(1)なので動的計画法を使用した方法より高速で、テストケースも全てパスします。