[LeetCode]题解（python）：093-Restore IP Addresses

题目来源：

　　https://leetcode.com/problems/restore-ip-addresses/

---

题意分析：

　　输入一个字符串，判断有多少种ip组合。比如，给定"25525511135"，返回["255.255.11.135", "255.255.111.35"]

---

题目思路：

　　要判断有多少种ip组合那么首先要知道，ip共有4个断，都是在0-255之间。那么题目可以理解成，在一个字符串里加入3个挡片，使得分成的4个子字符串的数值都小于255.这里可以用递归方法来做。solve（s，n）其中s是字符串，n是分成多少份。将s分别取1，2，3个字符，判断是否符合小于255，如果小于则判断solve(s[i:],n -1)是否满足的，如果有将s[:i]+solve(s[i:],n-1)。

---

代码（Python）：

　　

class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        def solve(s,n):
            if s == '':
                return []
            if n == 1:
                if len(s) > 1 and s[0] == '0':
                    return []
                elif int(s) <= 255:
                    return [s]
                else:
                    return []
            ans = []
            if s[0] == '0':
                tmp = solve(s[1:],n-1)
                for i in tmp:
                    ans.append('0.'+i)
            else:
                t = ''
                for i in range(3):
                    if i < len(s):
                        t += s[i]
                        if int(t) <= 255:
                            tmp = solve(s[i + 1:],n - 1)
                            for j in tmp:
                                ans.append(t + '.' +j)
            return ans
        return solve(s,4)

---

转载请注明出处：http://www.cnblogs.com/chruny/p/5088945.html