Restore IP Addresses

アルゴリズム概要

問題説明

数字のみから成る文字列 s に対し、3つのドットを挿入して4つのセグメントを作り、全ての有効なIPv4アドレスを列挙します。

制約条件

• 各セグメントは 0〜255 の整数
• 先頭ゼロ禁止（ただし単独の "0" は許可）
• 文字の順序変更・削除は不可（挿入のみ）
• 1 <= s.length <= 20

入出力例

Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]

Input: s = "0000"
Output: ["0.0.0.0"]

戦略のポイント

• 深さ優先探索（DFS）：各セグメントで1〜3桁を試行
• 残文字数の枝刈り：remainSegs <= remainChars <= remainSegs * 3 で不可能な分岐を排除
• 先頭ゼロ処理：先頭が '0' なら長さ1のみ試行
• 255超過チェック：逐次数値化で255を超えたら即座にループ脱出
• キャッシュ参照：0〜255の文字列を事前に生成し、スライス生成を回避

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

Python実装

from __future__ import annotations
from typing import List

class Solution:
    """
    Restore IP Addresses（メモリ最適化版）
    - 0..255 の文字列を事前キャッシュして、部分文字列生成を回避
    - 固定長配列 path を再利用し、探索中の一時オブジェクトを最小化
    """

    # 共有キャッシュ：0〜255 を文字列化して再利用
    _SEG_CACHE: List[str] = [str(i) for i in range(256)]

    def restoreIpAddresses(self, s: str) -> List[str]:
        """
        全ての有効なIPv4アドレスを列挙

        Args:
            s: 数字のみから成る文字列

        Returns:
            生成可能な全ての有効IPv4アドレス（順不同）

        Raises:
            TypeError: 入力がstrでない、または数字以外を含む場合

        Complexity:
            Time: O(1)（n≤20、最大3^4分岐、出力を除く）
            Space: O(1)（path固定長のみ、出力を除く）
        """
        # 入力検証
        if not isinstance(s, str):
            raise TypeError("Input must be a string.")

        n: int = len(s)

        # 数字のみ許可
        for ch in s:
            if ch < '0' or ch > '9':
                raise TypeError("Input must contain digits only.")

        # IPv4は合計4〜12桁のみ成立
        if n < 4 or n > 12:
            return []

        res: List[str] = []
        path: List[str] = [""] * 4  # 固定長配列・再利用
        SEG = self._SEG_CACHE  # ローカル束縛で属性探索を削減

        def dfs(idx: int, seg: int) -> None:
            """
            深さ優先探索でセグメントを決定

            Args:
                idx: 現在の文字位置
                seg: 埋まったセグメント数（0〜4）
            """
            # 基底条件：4セグメント完成
            if seg == 4:
                if idx == n:
                    # 全文字使い切り → 有効なIP
                    res.append(".".join(path))
                return

            remain_segs = 4 - seg
            remain_chars = n - idx

            # 枝刈り：残文字数が不足または過剰
            if remain_chars < remain_segs or remain_chars > remain_segs * 3:
                return

            # 先頭が '0' なら長さ1のみ許可
            first_is_zero = s[idx] == '0'
            max_len = 1 if first_is_zero else 3

            val = 0  # セグメント数値を逐次生成
            for length in range(1, max_len + 1):
                if idx + length > n:
                    break

                # 逐次数値化：val = val*10 + digit
                val = val * 10 + (ord(s[idx + length - 1]) - 48)

                # 255超過したら以降は全て不正
                if val > 255:
                    break

                # キャッシュから文字列参照（スライス生成なし）
                path[seg] = SEG[val]
                dfs(idx + length, seg + 1)

        dfs(0, 0)
        return res

フローチャート

フローの説明：
1. 基底条件：4セグメント完成 + 全文字使用 → 結果に追加
2. 枝刈り：残文字数が不足/過剰なら即座に戻る
3. 長さ決定：先頭が '0' なら長さ1のみ、それ以外は1〜3を試行
4. 逐次数値化：ループ内で桁を加算（int()変換を回避）
5. 255チェック：超過したらループ脱出（以降は全て不正）
6. 再帰呼び出し：キャッシュから文字列参照し、次のセグメントへ
7. ループバック：次の長さを試行、全て試したら前のステップへ戻る

計算量分析

他手法との比較