Lexi's Leetcode solutions

[leetcode] restore ip address | 把一个string parse成valid ip地址,返回所有valid parse

Posted on: August 11, 2013

和电话号码一样,基本的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();
}
Advertisements
Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: