For example:
Given
"25525511135"
,
return
["255.255.11.135", "255.255.111.35"]
. (Order does not matter)
public class Solution { private List<String> result; private String[] strs; // IP field public List<String> restoreIpAddresses(String s) { // Backtracking problem result = new LinkedList<>(); int len = s.length(); if (len < 3) return result; strs = new String[4]; backTracking(s, 0, 0); return result; } // startPos --- Start position of IP field // cnt --- ID of IP field (0, 1, 2, 3) private void backTracking(String s, int startPos, int cnt) { if (cnt == 4) { if (startPos == s.length()) // Just use all of the given numbers. { String ret = strs[0]; for (int i = 1; i < 4; i++) { ret += "."; ret += strs[i]; } result.add(ret); } } else { // Note: Avoid overflow. for (int i = 1; i<=3 && startPos+i<=s.length(); i++) { strs[cnt] = s.substring(startPos, startPos+i); if (place(strs[cnt])) backTracking(s, startPos+i, cnt+1); } } } // Verify if this IP field is qualified or not. private boolean place(String str) { // e.g, "00", "021" are not qualified. if (str.length()>1 && str.charAt(0)=='0') return false; if (Integer.parseInt(str) <= 255) return true; else return false; } }
No comments:
Post a Comment