93. Restore IP Addresses 复原 IP 地址

@TOC

# 题目描述

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"]
``````

# 解题方法

# 回溯法

``````class Solution(object):
"""
:type s: str
:rtype: List[str]
"""
if len(s) > 12:
return []
res = []
self.dfs(s, [], res)
return res

def dfs(self, s, path, res):
if not s and len(path) == 4:
res.append('.'.join(path))
return
for i in range(1, 4):
if i > len(s):
continue
number = int(s[:i])
if str(number) == s[:i] and number <= 255:
self.dfs(s[i:], path + [s[:i]], res)
``````

``````class Solution(object):
"""
:type s: str
:rtype: List[str]
"""
res = []
self.dfs(s, [], res)
return res

def dfs(self, s, path, res):
if len(s) > (4 - len(path)) * 3:
return
if not s and len(path) == 4:
res.append('.'.join(path))
return
for i in range(min(3, len(s))):
curr = s[:i+1]
if (curr[0] == '0' and len(curr) >= 2) or int(curr) > 255:
continue
self.dfs(s[i+1:], path + [s[:i+1]], res)
``````

``````class Solution {
public:
if (s.size() > 12) return {};
vector<string> res;
helper(s, res, {}, 0);
return res;
}
void helper(const string& s, vector<string>& res, vector<string> path, int start) {
if (start > s.size() || path.size() > 4) return;
if (start == s.size() && path.size() == 4) {
res.push_back(path[0] + '.' + path[1] + '.' + path[2] + '.' + path[3]);
return;
}
for (int i = 1; i <= 3; i++) {
string sub = s.substr(start, i);
if (sub.size() == 0 || (sub.size() > 1 && sub[0] == '0') || stoi(sub) > 255) continue;
path.push_back(sub);
helper(s, res, path, start + i);
path.pop_back();
}
}
};
``````

# 日期

2018 年 6 月 11 日 —— 今天学科三在路上跑的飞快～ 2018 年 12 月 22 日 —— 今天冬至