本文共 2116 字,大约阅读时间需要 7 分钟。
题目描述:给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135"输出:["255.255.11.135", "255.255.111.35"]
解法1。暴力解法,用4个变量分别从[1,4)遍历,再由此确定4个分段的下标
class Solution(object): def restoreIpAddresses(self, s): """ :type s: str :rtype: List[str] """ if not s or len(s) > 12: return [] res = [] for a in range(1,4): for b in range(1,4): for c in range(1,4): for d in range(1,4): if a+b+c+d == len(s): # 这一句一定要注意,必须要加,只有满足此条件时才有效,大于会超index,小于无效 ip_s = '' A = int(s[:a]) B = int(s[a:a+b]) C = int(s[a+b:a+b+c]) D = int(s[a+b+c:a+b+c+d]) if A <= 255 and B <= 255 and C <= 255 and D <= 255: ip_s = str(A)+'.'+str(B)+'.'+str(C)+'.'+str(D) if len(ip_s) == len(s)+3 and ip_s not in res: res.append(ip_s) return res
解法2。用递归的解法。隐约觉得这个思路就是人思考的思路,从第一个子串开始,其变化范围为[1,4),先判断这个子串是否有效,然后递归下去看下一个子串,而这下一个子串的判断思路和上一个一样,也需要经过for循环,变化范围为[1,4),再加上一些有效的判断条件,用k值记录字还剩下几个字符串要判断,这个思路也可以改成[0,4]来判断,
class Solution(object): def restoreIpAddresses(self, s): """ :type s: str :rtype: List[str] """ if not s or len(s) > 12 or len(s) < 4: return [] res = [] out = '' k = 4 self.restore(s, k, out, res) return res def restore(self, s, k, out, res): if k == 0: if not s: res.append(out) else: for i in range(1,4): if len(s) >= i and self.isValid(s[:i]): if k == 1: self.restore(s[i:], k-1, out + s[:i], res) else: self.restore(s[i:], k-1, out+s[:i]+'.', res) def isValid(self, s): if not s or len(s)>3 or (len(s)>1 and s[0]=='0'): return False res = int(s) return res <= 255 and res >= 0
参考链接:
转载地址:http://vufo.baihongyu.com/