給定一個只包含數字的字串
s，回傳所有可能的合法 IPv4 地址。合法 IP 地址由四個 0 到 255 的整數組成，用 ’.’ 分隔，且整數不能有前導零（除了 “0” 本身）。
Example:
Input: s = “25525511135” Output: [“255.255.11.135”,“255.255.111.35”]
Intuition
TIP
核心思路：回溯法在字串中嘗試放置 3 個分隔點，每段需滿足 IP 地址規則。
- IP 地址有 4 段，每段 1
3 個字元，值在 0255 之間，無前導零 - 回溯：每次嘗試切 1~3 個字元作為一段，驗證合法性後遞迴
- 當已切出 4 段且剛好用完所有字元時，收集結果
Approaches
1. Brute Force: Enumerate Three Cut Points — O(3^4) / O(1)
- Idea: 三層迴圈枚舉前三段長度（各 1~3），第四段由剩餘長度決定，驗證四段皆合法
- Time:
O(3^3)種切法 × 常數驗證 =O(1)（固定上界） - Space:
O(1)
class Solution {
fun restoreIpAddresses(s: String): List<String> {
val res = mutableListOf<String>()
val n = s.length
if (n < 4 || n > 12) return res
for (a in 1..3) for (b in 1..3) for (c in 1..3) {
val d = n - a - b - c
if (d < 1 || d > 3) continue
val p1 = s.substring(0, a)
val p2 = s.substring(a, a + b)
val p3 = s.substring(a + b, a + b + c)
val p4 = s.substring(a + b + c)
if (valid(p1) && valid(p2) && valid(p3) && valid(p4)) {
res.add("$p1.$p2.$p3.$p4")
}
}
return res
}
private fun valid(seg: String): Boolean {
if (seg.length > 1 && seg[0] == '0') return false // 前導零
return seg.toInt() <= 255
}
}⭐ 2. Backtracking — O(3^4) / O(1)
- Idea: 遞迴嘗試每段取 1~3 位數，驗證合法性，切滿 4 段且字串用完即為合法結果
- Time:
O(3^4)=O(81)- 每段最多 3 種切法，共 4 段 - Space:
O(1)- 固定深度 4
class Solution {
fun restoreIpAddresses(s: String): List<String> {
val result = mutableListOf<String>()
val segments = mutableListOf<String>()
fun backtrack(start: Int) {
if (segments.size == 4) {
if (start == s.length) {
result.add(segments.joinToString("."))
}
return
}
for (len in 1..3) {
if (start + len > s.length) break
val segment = s.substring(start, start + len)
// 前導零檢查：長度 > 1 但以 '0' 開頭
if (segment.length > 1 && segment[0] == '0') break
// 範圍檢查
if (segment.toInt() > 255) break
// 剩餘長度檢查
val remaining = s.length - start - len
val segmentsLeft = 3 - segments.size
if (remaining < segmentsLeft || remaining > segmentsLeft * 3) continue
segments.add(segment)
backtrack(start + len)
segments.removeAt(segments.lastIndex)
}
}
backtrack(0)
return result
}
}🔑 Takeaways
- Pattern: 字串分割問題 → 回溯法逐段切割並驗證
- Key trick: 三個驗證條件（前導零、範圍 0-255、剩餘長度足夠）；因為 IP 固定 4 段且每段最多 3 位，搜索空間極小（常數級）。類似 131. Palindrome Partitioning 的分割策略