_93.java

package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.List;

/**
 * 93. Restore IP Addresses
 *
 * 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)
 */
public class _93 {

  public static class Solution1 {
    public List<String> restoreIpAddresses(String s) {
      List<String> allValidIpAddresses = new ArrayList<>();
      if (s == null || s.length() > 12 || s.length() < 4) {
        return allValidIpAddresses;
      }
      backtracking(s, new ArrayList<>(), allValidIpAddresses, 0);
      return allValidIpAddresses;
    }

    private void backtracking(String s, ArrayList<String> bytes, List<String> result, int pos) {
      if (bytes.size() == 4) {
        if (pos != s.length()) {
          return;
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < 4; i++) {
          stringBuilder.append(bytes.get(i));
          stringBuilder.append(".");
        }
        stringBuilder.setLength(stringBuilder.length() - 1);
        result.add(stringBuilder.toString());
        return;
      }

      for (int i = pos; i < pos + 4 && i < s.length(); i++) {
        String oneByte = s.substring(pos, i + 1);
        if (!isValid(oneByte)) {
          continue;
        }
        bytes.add(oneByte);
        backtracking(s, bytes, result, i + 1);
        bytes.remove(bytes.size() - 1);
      }
    }

    private boolean isValid(String oneByte) {
      if (oneByte.charAt(0) == '0') {
        return oneByte.equals("0");
      }
      int num = Integer.valueOf(oneByte);
      return (num >= 0 && num < 256);
    }
  }
}