Leetcode[93] Restore IP Addresses
07 Nov 2015###Task1 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)
###Python
class Solution(object):
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
ret = []
if len(s) > 12:
return ret
self.findAll(s, ret, '', 0, 0)
return ret
def findAll(self, s, ret, cur, pos, num):
if num == 4 and pos == len(s):
ret.append(cur[:])
for i in range(pos + 1, len(s) + 1):
if self.isValid(s[pos : i]):
if pos == 0:
self.findAll(s, ret, cur + s[pos : i], i, num + 1)
else:
self.findAll(s, ret, cur + '.' + s[pos : i], i, num + 1)
def isValid(self, s):
if len(s) > 1 and s[0] == '0':
return False
return int(s) >= 0 and int(s) <= 255
###Java
public class Solution {
public boolean isValid(String s) {
if (s.charAt(0) == '0' && s.length() > 1) {
return false;
}
int num = Integer.parseInt(s);
return num >= 0 && num <= 255;
}
public void restoreHelper(List<String> res, String s, int pos, StringBuilder sb, int times) {
if (sb.length() == s.length() + 3 && times == 4) {
String temp = sb.toString();
res.add(temp);
return;
} else {
for (int i = 1; i <= 3 && pos + i <= s.length(); i++) {
if (isValid(s.substring(pos, pos + i))) {
if (sb.length() != 0) {
sb.append(".");
}
sb.append(s.substring(pos, pos + i));//i element
restoreHelper(res, s, pos + i, sb, times + 1);
sb.delete(sb.length() - i, sb.length());
if (sb.length() != 0) {
sb.delete(sb.length() - 1, sb.length());
}
}
}
}
return ;
}
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<String>();
if (s == null || s.length() == 0 || s.length() > 12) {
return res;
}
StringBuilder sb = new StringBuilder();
restoreHelper(res, s, 0, sb, 0);
return res;
}
}
###Points
- Find all –> DFS
- End Condition: no more string to match && ret contains 4 segments
可以看出这棵树的规模是固定的，不会像平常的NP问题那样，时间复杂度取决于输入的规模，是指数量级的，所以这道题并不是NP问题，因为他的分支是四段，有限制”