题解 | #数字字符串转化成IP地址#

#
# 
# @param s string字符串 
# @return string字符串一维数组
#

def isValid(s):
    if int(s)<=255: 
        if s.startswith("0") and len(s)==1:
            return True
        if not s.startswith("0"):
            return True
        return False
def getPart(arr,start,end,level):# 传入的参数必须保证start < end
    if start<end:
        if level ==4:
        #已经到最后，验证剩下的数字是否符合，不符合，返回None
            if isValid(arr[start:end]):
                part = [[arr[start:end]]]
                return part #[[2],[3]]
            return [None]
        else:
            res = []
            if start + 1 <= len(arr): 
                if isValid(arr[start:start+1]):
                    part = arr[start:start+1]
                    p1 = getPart(arr, start+1, end, level+1)
                    for p in p1:
                        if p is not None:
                            p.insert(0, part)
                            res.append(p)

            if start + 2 <= end: 
                if isValid(arr[start:start+2]):
                    part = arr[start:start+2]
                    p1 = getPart(arr, start+2, end, level+1)
                    for p in p1:
                        if p is not None:
                            p.insert(0, part)
                            res.append(p)
            if start + 3 <= end: 
                if isValid(arr[start:start+3]):
                    part = arr[start:start+3]
                    p1 = getPart(arr, start+3, end, level+1)
                    for p in p1:
                        if p is not None:
                            p.insert(0, part)
                            res.append(p)
            return res

    else:
        return [None]

class Solution:
    def restoreIpAddresses(self , s ):
        # write code here
        if s is None or s=="": return []
        res = getPart(s, 0, len(s), 1) #[[225,23,23,23],[...],[...]]
        return [".".join(r) for r in res if r is not None]