首页 > 代码库 > LeetCode 93. Restore IP Addresses 20170705 部分之前做了没写的题目

LeetCode 93. Restore IP Addresses 20170705 部分之前做了没写的题目

 

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

题目大意:给出一串数字组成的字符串,返回所有可能的有效的IP地址组合

解题思路:同样还是深度优先的办法。先看看终止条件,先用一个count来保存IP地址有几段。有效的IP地址总共有四段,所以当count等于4的时候才是有效的,且当count等于4时,该字符串应该已经读完了,所以还加一个条件是如果s==‘‘,此时添加临时保存IP地址的字符串到结果集合中。这里只返回从下标为1开始的字符串是因为根据后面的代码,会在IP地址的每一段前面加一个点,第一段前面的点应该被省略。下面的dfs循环,每一段IP地址都是小于255的,所以每一段地址有可能是1位、2位、3位数字,因此在每一段地址的时候都分成1、2、3位数字三种情况,且这些数字都要小于255,如果符合条件,则下一个循环中原数组s舍弃掉该段IP地址的数字,在临时保存IP地址字符串中加一个点和该段的数字。如果碰到当前s的第一位是0,则该段IP地址只可能是0,就不需要再作1、2、3位的循环了,直接跳出循环。

技术分享

class Solution:
  def restoreIpAddresses(self, s):
    """
    :type s: str
    :rtype: List[str]
    """
    def dfs(s, count, List):
      if count == 4:
        if s == ‘‘:
          A.append(List[1:len(List)])
      return
      for i in range(1, 4):
        if i <= len(s):
          if int(s[0:i]) <= 255:
            dfs(s[i:len(s)], count+1, List+‘.‘+s[0:i])
          if s[0] == ‘0‘: break
    A = []
    dfs(s, 0, ‘‘)
    return A

LeetCode 93. Restore IP Addresses 20170705 部分之前做了没写的题目