【回溯】leetcode93.复原IP地址

题目&＃xff1a;
给定一个只包含数字的字符串 s &＃xff0c;用以表示一个 IP 地址&＃xff0c;返回所有可能从 s 获得的 有效 IP 地址 。你可以按 任何 顺序返回答案。

有效 IP 地址 正好由四个整数&＃xff08;每个整数位于 0 到 255 之间组成&＃xff0c;且不能含有前导 0&＃xff09;&＃xff0c;整数之间用 ‘.’ 分隔。

例如&＃xff1a;“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址&＃xff0c;但是 “0.011.255.245”、“192.168.1.312” 和 “192.168&＃64;1.1” 是 无效 IP 地址。

解答&＃xff1a;

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:res&＃61;[]path&＃61;[]def tracebacking(s,startidx):nonlocal res,pathif startidx&＃61;&＃61;len(s) and len(path)&＃61;&＃61;4:res.append(&＃39;.&＃39;.join(path))#i:从s[i]后分割字符串for i in range(startidx,len(s)): #&＃39;0&＃39;打头&＃xff0c;只能单独存在if s[startidx]&＃61;&＃61;&＃39;0&＃39; and i!&＃61;startidx:breaknum&＃61;int(s[startidx:i&＃43;1])if num>&＃61;0 and num<&＃61;255:path.append(s[startidx:i&＃43;1])tracebacking(s,i&＃43;1)path.pop()else:break n&＃61;len(s)if n&＃61;&＃61;0 or n>12:return restracebacking(s,0)return res