Restore IP Addresses
Problem:
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given
Given
"25525511135"
,
return
["255.255.11.135", "255.255.111.35"]
. (Order does not matter)
Analysis:
It's very similar to palindrome-partitioning, but implementation has to be very careful with corner cases.
Solution:
items.size() > 4 is critical to backtrack.
class Solution { public List<String> restoreIpAddresses(String s) { List<String> res = new ArrayList<>(); if (s.length() < 4 || s == null) return res; helper(res, new ArrayList<>(), s); return res; } private void helper (List<String> res, List<String> items, String s) { if (items.size() == 4 && s.length() == 0) { res.add(convert(items)); return; } if (items.size() > 4 ) return; for (int i = 0; i < 3 && i < s.length(); i++) { String item = s.substring(0, i + 1); if ((item.charAt(0) == '0' && item.length() > 1) ||
Integer.parseInt(item) > 255) continue; items.add(item); helper(res, items, s.substring(i+1)); items.remove(items.size() - 1); } } private String convert(List<String> items) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < 4; i++) { String s = items.get(i); if (i == 3) sb.append(s); else sb.append(s + "."); } return sb.toString(); } }
评论
发表评论