NeetCode 150 [Sliding Window]:medium 3/3

NeetCodeのSolutionを書いていく

Permutation in String

問題概要

文字列s1とs2が与えられます。
s2がs1の順列を含む場合はtrueをそれ以外であればfalseを返しましょう。
文字列はすべて小文字です。
順列とは「ある集合を並べ替えた時の並び」です。

例

Input: s1 = "abc", s2 = "lecabee"
Output: true

"cab"は"abc"の順列なのでtrue

Input: s1 = "abc", s2 = "lecaabee"
Output: false

制約

s1もs2も長さは1以上1000以下。
計算時間：O(n)
メモリ：O(1)

メモ

自分の回答。
うーむわかりにくい。

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        l = r = 0
        s1_dict: dict[str, int] = {}

        for c in s1:
            s1_dict[c] = s1_dict.get(c, 0) + 1
        s1_dict_copy = s1_dict.copy()

        r = -1
        while True:
            r += 1
            if r == len(s2):
                return False

            # l~r間がs1の長さを超えたらlをずらす必要がある
            if r - l + 1 > len(s1):
                # ずらすときは、文字カウンターを戻す
                if s2[l] in s1_dict:
                    s1_dict[s2[l]] += 1
                l += 1

            # rの文字がs1にあるかチェック
            v = s1_dict.get(s2[r])
            # ない場合は、その文字は使えないので、s1_dictをリセットして次に進む
            if v is None:
                s1_dict = s1_dict_copy.copy()
                l = r + 1  # この時lも次のrと同じ位置を指すようにする
                continue

            # ある場合で、既に文字列数を使い果たしている場合は
            if s1_dict[s2[r]] == 0:
                l += 1  # lをずらす必要がある
                s1_dict[s2[l]] += 1  # ずらした文字のカウントを戻す
                r -= 1  # rはもう一度評価するために一つ前に戻す
                continue

            # 文字カウントを減らす
            s1_dict[s2[r]] -= 1

            # 全部0になったらTrue
            if not any(s1_dict.values()):
                return True

chatgptの回答！
わかりやすい！

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        from collections import Counter
        len1, len2 = len(s1), len(s2)

        # 変更点1: s1 の長さが s2 より大きい場合は順列が存在しないので False を返す
        if len1 > len2:
            return False

        # 変更点2: s1 の文字カウントを Counter で取得
        count1 = Counter(s1)
        # 変更点3: s2 の最初のウィンドウ（長さ len1）のカウントを取得
        window_count = Counter(s2[:len1])

        # 変更点4: 初期ウィンドウで s1 のカウンターと一致するか検証
        if count1 == window_count:
            return True

        # 変更点5: ウィンドウをスライドさせながら更新
        for i in range(len1, len2):
            # 変更点6: ウィンドウに新たに加わる文字のカウントを更新
            window_count[s2[i]] += 1
            # 変更点7: ウィンドウから外れる文字のカウントをデクリメント
            window_count[s2[i - len1]] -= 1
            # 変更点8: カウントが 0 の場合はキーを削除してクリーンに保つ
            if window_count[s2[i - len1]] == 0:
                del window_count[s2[i - len1]]
            # 変更点9: 現在のウィンドウと s1 のカウンターが一致すれば順列が存在するので True を返す
            if count1 == window_count:
                return True

        # 変更点10: 一致するウィンドウがなければ False を返す
        return False