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 部分之前做了没写的题目