【leetcode】93. 複原IP位址

題目

給定一個隻包含數字的字元串，複原它并傳回所有可能的 IP 位址格式。

示例:

輸入: “25525511135”

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

解題思路

ip位址分為四節，每節取值範圍在[0,255]

對于取出的字元串，若它的第一位為’0’，那麼它的長度隻能為1，多位字元不能以0作為開頭

每次拿出[1,3]個字元，判斷是否符合ip位址的條件，若符合，則遞歸剩下的字元串，直到四節都符合，那麼就得到了一個解

def isTrue(s):
    #首先判斷是否以0開頭
    if s.find("0")==0:
        if len(s)>=2:
            return False
        else:
            return True
    else:
        if int(s)>255:
            return False
        else:
            return True

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        s_len=len(s)
        if s_len>12 or s_len==0:
            return []
        def solve(s,k):
            # k 目前已經找到幾個了
            res=[]
            if k==3:
                if len(s)>3 or len(s)==0 or isTrue(s)==False:
                    return []
                else:
                    return [[s]]
            else:
                for i,c in enumerate(s):
                    if i>=3:
                        break
                    if isTrue(s[0:i+1]):                        
                        for tmp in solve(s[i+1:],k+1):
                            head_l=[s[0:i+1]]
                            head_l.extend(tmp)
                            res.append(head_l)
                    else:
                        break
            return res
        res=[".".join(a) for a in solve(s,0)]
        return res