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"]
这个题目因为是要求所有的具体结果，所以需要用search， 考虑DFS，然后类似于[LeetCode] 131. Palindrome Partitioning_Medium tag: DFS, backtracking, Palindrome， 将它看成要加4刀使得符合“IP”的格式，每个要么是一位，如果2位，需要[10, 99], 如果3位，需要[100, 255]. 所以只是把palin() 改成了isValid()函数而已。
class Solution: def restoreIp(self, s):
n = len(s)
if n < 3 or n > 12: return False ans = [] def isValid(start, end, s): num = int(s[start: end + 1]) if end > start + 2: return False elif end == start: return True elif end == start + 1: return 10 <= num <= 99 else: return 100 <= num <= 255 def helper(s, temp, ans, pos): if pos == len(s) and len(temp) == 4: ans.append(‘.‘.join(temp)) for i in range(pos, len(s)): if len(temp) < 3 and isValid(pos, i, s): helper(s, temp + [s[pos: i + 1]], ans, i + 1) helper(s, [], ans, 0) return ans
[LeetCode] 93. Restore IP Addresses_Medium tag: backtracking
原文：https://www.cnblogs.com/Johnsonxiong/p/11155675.html