Lexi's Leetcode solutions

和电话号码一样，基本的DFS。mark一下，下次再准备面试的时候可能就忘了这种题型了。

public ArrayList<String> restoreIpAddresses(String s) {
  ArrayList<String> result = new ArrayList<String>();
  String[] curr = new String[4];
  restore(s, 0, curr, result);
  return result;
}
private void restore(String s, int level, String[] curr, ArrayList<String> result) {
  if (level == 4) {
    if (s.isEmpty()) {
      result.add(convertToIpString(curr));
    }
    return;
  } else if (s.isEmpty())
  return;
 
  for (int i = 1; i <= 3 && i <= s.length(); i++) {
    String left = s.substring(0, i);
    String right = s.substring(i);
    if (validIp(left)) {
      curr[level] = left;
      restore(right, level+ 1, curr, result);
    }
  }
}
private boolean validIp(String s) {
  if (s.length() > 1 && s.charAt(0) == '0')
    return false;
  return Integer.valueOf(s) < 256;
}
private String convertToIpString(String[] curr) {
  StringBuilder sb = new StringBuilder();
  for (String s : curr) {
    sb.append(s);
    sb.append(".");
  }
  sb.deleteCharAt(sb.length() - 1);
  return sb.toString();
}