93. 復(fù)原IP地址
題目來(lái)源：力扣（LeetCode）https://leetcode-cn.com/problems/restore-ip-addresses
題目
給定一個(gè)只包含數(shù)字的字符串，復(fù)原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四個(gè)整數(shù)（每個(gè)整數(shù)位于 0 到 255 之間組成），整數(shù)之間用 '.' 分隔。
示例:
輸入: "25525511135"
輸出: ["255.255.11.135", "255.255.111.35"]
解題思路
思路： 回溯
先看題目，題目要求的是給定一個(gè)只包含數(shù)字的字符串，復(fù)原返回所有可能的 IP 地址格式。至于 IP 地址的有效格式，是由 4 個(gè)整數(shù)（0~255），整數(shù)間用 '.' 分隔組成。
首先，根據(jù)題目，借助示例來(lái)看下：
s = "25525511135"
假設(shè)，給定的字符串如上面示例，那么我們?cè)诘谝粋€(gè)片段中，我們有三種選擇的可能：
- 選 '2'；
- 選 '25'；
- 選 '255'。
當(dāng)?shù)谝黄芜x擇完畢后，后續(xù)的三個(gè)片段，也以同樣的形式去選擇。但是我們?cè)谶x擇的過(guò)程中可能會(huì)出錯(cuò)，如果出錯(cuò)的話，此時(shí)我們就需要撤銷這項(xiàng)選擇，轉(zhuǎn)而去嘗試另外一個(gè)選擇。
同樣的，這里我們的選擇是有依據(jù)的，并非隨意選擇。由題目，我們也可以發(fā)現(xiàn)，每個(gè)片段可選擇的數(shù)字區(qū)間在 [0, 255] 之間，這里也表示長(zhǎng)度不能超過(guò) 3。
這里還有個(gè)需要注意的，題目中并沒(méi)有明確指出。每個(gè)片段中選擇的數(shù)字是不能有前導(dǎo) 0 的，0 可以作為一個(gè)選擇，但是不能出現(xiàn) '0...' 這樣的形式，這個(gè)也是在測(cè)試用例沒(méi)過(guò)的時(shí)候發(fā)現(xiàn)的。╮(╯▽╰)╭
前面說(shuō)了選擇以及限制，那我們?nèi)绾尾拍艽_認(rèn)，當(dāng)選擇完畢之后，選擇組成的片段就是有效的？
- 首先，要在前面所述的限制條件下進(jìn)行選擇；
- 再來(lái)，題目要求復(fù)原，也就是，我們選擇完 4 個(gè)片段之后，必須是要用完所有字符的。
- 如果選擇完畢，但是沒(méi)有用完字符，表示此項(xiàng)選擇不符合，返回，回溯；如果先用完字符，但是沒(méi)有找齊 4 個(gè)片段，同樣回溯。
- 因?yàn)閺?fù)原的結(jié)果可能不止一種，當(dāng)找到有效的組合，存入返回列表中，繼續(xù)搜索直至所有可能的選擇都嘗試一次。
具體的代碼實(shí)現(xiàn)如下（含注釋）。
代碼實(shí)現(xiàn)
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
# 這里初始化長(zhǎng)度為 4 的列表，分別存儲(chǔ)對(duì)應(yīng) 4 個(gè)片段
sub_res = [0] * 4
def dfs(seg_id, seg_first):
# 先看找到 4 個(gè)片段的情況
# 這里可能出現(xiàn)字符完全使用，以及未使用完全的情況
if seg_id == 4:
# 使用完全則添加到列表后返回
if seg_first == len(s):
res.append('.'.join(str(seg)for seg in sub_res))
# 未完全使用則直接返回
return
# 若未找到 4 個(gè)片段，則繼續(xù)查找
# 這里要注意未找到 4 個(gè)片段卻使用完字符的情況
if seg_first == len(s):
return
# 不能存在前導(dǎo) 0，如果有 0，那么當(dāng)前片段只能為單獨(dú) 0
if s[seg_first] == "0":
sub_res[seg_id] = 0
dfs(seg_id+1, seg_first+1)
addr = 0
# 每個(gè)片段選擇的情況
for seg_last in range(seg_first, len(s)):
# 這里用整型來(lái)表示，后面再轉(zhuǎn)換為字符串類型，避免過(guò)于頻繁的切片
addr = addr * 10 + (ord(s[seg_last]) - ord('0'))
# 大于 0，但小于等于 255 的情況
if 0 < addr <= 255:
sub_res[seg_id] = addr
dfs(seg_id+1, seg_last+1)
# 其他情況直接跳出循環(huán)
else:
break
dfs(0, 0)
return res
實(shí)現(xiàn)結(jié)果
歡迎關(guān)注
公眾號(hào) 【書(shū)所集錄】
