57. Is Subsequence

読了目安約2分

その他 / LeetCode 392 (Easy) — s が t の部分列かを判定する

この章の目次

問題

LeetCode 392. Is Subsequence（Easy / カテゴリ: その他）

2 つの文字列 s と t が与えられます。 t から文字をいくつか削除し、残りの順序を変えずに s を作れるかを Bool で返します。

このように順序を保って取り出せる文字列を部分列と呼びます。連続して並んでいる必要はありません。空文字列はどの文字列の部分列でもあります。

考え方

ヒント 1

t を先頭から 1 回走査するだけで判定できます。 s 側の「次に一致させたい文字」を覚えておきます。

ヒント 2

添字 i を「s の何文字目まで一致したか」とします。 t の文字が s の i 文字目と等しいたびに i を進め、走査後に i == s.count なら部分列です。一致できる最初の位置で貪欲に一致させても、後の一致の機会は減りません。

Swift 実装のポイント

Swift の String は整数の添字で直接引けません。Array(s) で [Character] に変換してから sChars[i] と参照します。
t 側は先頭から順に見るだけなので、変換せず for ch in t で走査できます。
i が s.count に達した後も走査は続きます。sChars[i] を読む前に i < sChars.count を確認しないと範囲外アクセスです。

模範解答

Swift
class Solution {
    func isSubsequence(_ s: String, _ t: String) -> Bool {
        let sChars = Array(s)
        var i = 0
        for ch in t {
            if i < sChars.count && ch == sChars[i] {
                i += 1
            }
        }
        return i == sChars.count
    }
}

計算量: O(t の長さ)。