leetcode(力扣) 93. 複原 IP 位址（回溯）

文章目錄

• ​​題目描述​​
• ​​思路分析​​
• ​​完整代碼​​

題目描述

有效 IP 位址 正好由四個整數（每個整數位于 0 到 255 之間組成，且不能含有前導 0），整數之間用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 位址，但是 “0.011.255.245”、“192.168.1.312” 和 “[email protected]” 是 無效 IP 位址。

給定一個隻包含數字的字元串 s ，用以表示一個 IP 位址，傳回所有可能的有效 IP 位址，這些位址可以通過在 s 中插入 ‘.’ 來形成。你 不能 重新排序或删除 s 中的任何數字。你可以按 任何 順序傳回答案。

示例 1：

輸入：s = “25525511135”

輸出：[“255.255.11.135”,“255.255.111.35”]

示例 2：

輸入：s = “0000”

輸出：[“0.0.0.0”]

示例 3：

輸入：s = “101023”

輸出：[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]

思路分析

一定要。

先做 ​​31. 分割回文串​​ 再做這道題！！！

先做 ​​31. 分割回文串​​ 再做這道題！！！

先做 ​​31. 分割回文串​​ 再做這道題！！！

為啥呢~因為這道題是分割回文串的進階版，改動的地方不多。

這道題也是分割，而且比上一個字元串分割感覺看上去要清晰一些，也是找組合的題嘛，回溯嘛，你要問我能不能暴力，我隻能說， 可以暴力，看到有人這麼做了，N層for，寫到懷疑人生。

判斷IP位址合法性的幾個點：

• IP位址一共是四段組成，中間三個 ‘.’ 分隔符。
• 每一段有0-3個數字，範圍是0-255左閉右閉。
• 每小段中可以僅有0，但不能有向導0。

def ip_check(ip):
        if ip == '0':return True  # 可以有0但不能前導0
        if ip[0] == '0':return False
        if int(ip) > 0 and int(ip) < 256:
            return  True
        else:
            return False      

老規矩 回溯三步走：

1.确定函數參數：

這裡的參數非常簡單，就一個值，就是startindex，用于記錄下次從哪裡開始周遊。當然，這個參數确定要參考所寫代碼結構和所用程式設計語言。

2.确定終止條件：

如果path裡有4個值了，也就是有4個小段ip了，并且 startindex 已經周遊到最後了，那麼此時就加入到答案集res裡。

這道題最後有兩個小提示，

​

​1 <= s.length <= 20​

​​

​s 僅由數字組成​

​

這就意味着在判斷ip合法性的時候不需要判斷是否是數字字元了。

還有一點就是題目要求不得删改原s字元中的數值，但是題目s所給長度範圍又達到20個，而合法ip最大長度也就是每一段都是3個字元，是以最長也就是12個字元，在這裡可以設定一個終止條件，就是所給s長度大于12，則直接return。

完整代碼

def restoreIpAddresses(self, s: str):
    path = []
    res = []
    def ip_check(ip):
        if ip == '0':return True  # 可以有0但不能前導0
        if ip[0] == '0':return False
        if int(ip) > 0 and int(ip) < 256:
            return  True
        else:
            return False
    def backtrack(startindex):
        # 确定終止條件
        if len(s) > 12:  # 剪枝，題目所給的s長度為1-20.
            return
        if len(path) == 4 and startindex == len(s):
            res.append(".".join(path[:]))
            return
        # 遞歸體
        for i in range(len(startindex,len(s))):
            ip = s[startindex,i+1]
            if ip_check(ip):
                path.append(ip)
            else:
                continue
            backtrack(i+1)
            ip.pop()
    backtrack(0)
    return res