93.py

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

 Example:

 Input: "25525511135"
 Output: ["255.255.11.135", "255.255.111.35"]
'''

classSolution(object):
defrestoreIpAddresses(self, s):
"""
 :type s: str
 :rtype: List[str]
 """
result= []

defdfs(s, temp, count):
ifcount==4:
ifnots:
result.append(temp[:-1])
return

forindexinrange(1, 4):
ifindex<=len(s):
ifindex==1:
dfs(s[index:], temp+s[:index] +".", count+1)
elifindex==2ands[0] !='0':
dfs(s[index:], temp+s[:index] +".", count+1)
elifindex==3ands[0] !='0'andint(s[:3]) <=255:
dfs(s[index:], temp+s[:index] +".", count+1)

dfs(s, "", 0)
returnresult