97. Interleaving String

アルゴリズム概要

問題の説明

3つの文字列 s1、s2、s3 が与えられます。 s3 が s1 と s2 の interleaving（交互配置） で構成できるか判定します。

Interleaving とは、2つの文字列をそれぞれ部分文字列に分割し、元の順序を保ちながら交互に結合したものです。

入出力例

入力: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
出力: true
説明: s1 を "aa" + "bc" + "c" に分割し、s2 を "dbbc" + "a" に分割すると、
     "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac" が得られる

入力: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
出力: false
説明: どのように交互配置してもs3を構成できない

制約条件

• 0 ≤ s1.length, s2.length ≤ 100
• 0 ≤ s3.length ≤ 200
• すべて小文字英字のみ

戦略の説明

• 1次元 DP（動的計画法）を使用して空間計算量を最適化
• dp[j]: s1の先頭i文字とs2の先頭j文字でs3の先頭i+j文字を構成できるか
• 短い方の文字列を列方向に配置してメモリ効率を向上
• 各位置で「s1から遷移」または「s2から遷移」の論理和を取る

主要ポイント

• 時間計算量: O(len(s1) × len(s2))
• 空間計算量: O(min(len(s1), len(s2))) - Follow-up要件を満たす
• 最適化手法: 2D DP を 1D に圧縮、短い文字列を列方向に配置

ステップバイステップ解説

Python実装

from __future__ import annotations
from typing import List


class Solution:
    """
    Interleaving String 判定クラス（LeetCode 用）

    Time Complexity:
        O(len(s1) * len(s2))

    Space Complexity:
        O(min(len(s1), len(s2)))  # 1次元DP
    """

    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        """
        s3 が s1 と s2 の interleaving で構成できるかどうかを判定する。

        Args:
            s1: 1つ目の文字列
            s2: 2つ目の文字列
            s3: 判定対象の文字列

        Returns:
            s3 が s1 と s2 の interleaving なら True、それ以外は False
        """
        n1: int = len(s1)
        n2: int = len(s2)
        n3: int = len(s3)

        # 長さが合わなければ不可能
        if n1 + n2 != n3:
            return False

        # dp の列方向（長さ）を常に「短い方の文字列」にする
        # → dp のサイズ縮小 + 内側ループ回数も減少
        if n2 > n1:
            # s1 を「長い方」、s2 を「短い方」に揃える
            s1, s2 = s2, s1
            n1, n2 = n2, n1

        # dp[j]: s1 の先頭 i 文字と s2 の先頭 j 文字で s3 の先頭 i+j 文字を作れるか
        dp: List[bool] = [False] * (n2 + 1)

        # i = 0 行（s1 を 0 文字使用）の初期化
        dp[0] = True
        for j in range(1, n2 + 1):
            dp[j] = dp[j - 1] and (s2[j - 1] == s3[j - 1])

        # i >= 1 行の更新
        for i in range(1, n1 + 1):
            # j = 0 列（s2 を 0 文字使用）の更新
            dp[0] = dp[0] and (s1[i - 1] == s3[i - 1])

            for j in range(1, n2 + 1):
                k: int = i + j - 1  # s3 のインデックス

                # 上から来る: s1 の文字を使う
                from_s1: bool = dp[j] and (s1[i - 1] == s3[k])
                # 左から来る: s2 の文字を使う
                from_s2: bool = dp[j - 1] and (s2[j - 1] == s3[k])

                dp[j] = from_s1 or from_s2

        return dp[n2]

フローチャート

フローの説明：
1. まず n1 + n2 == n3 をチェック（不一致なら即 False）
2. n2 > n1 なら swap して、短い方を列方向に配置
3. dp 配列を初期化し、i=0 行（s2 のみ使用）を設定
4. i=1..n1 の各行で、j=0 列を更新後、j=1..n2 をループ
5. 各 dp[j] は「s1 から遷移」または「s2 から遷移」の論理和
6. すべてのループ完了後、dp[n2] を返却

計算量分析

時間計算量

O(len(s1) × len(s2))

• 外側ループ: i = 1..n1（n1回）
• 内側ループ: j = 1..n2（n2回）
• 各ステップは定数時間の比較と代入のみ

空間計算量

O(min(len(s1), len(s2)))

• DP 配列のサイズ: min(n1, n2) + 1
• Follow-up の要件「O(s2.length)」を満たす
• 短い方を列方向に配置する最適化により実質 O(min)

手法比較表