字节跳动面试算法题——还原IP地址

题目

给定一个只包含数字的字符串，用以表示一个IP（IPV4）地址，返回所有的有效IP 地址

• IPV4
• 192.168.111.111有效
• 192.168.111.011和192.168.111.256无效
• 例如：
  • 输入：19216811122
  • 输出：192.168.11.122, 192.168.111.22

分析

• IPV4共4段，每段数值在[0,255]区间内，使用"."分割
• 每段数值的位数在[1,3]区间内，计算每段数值的位数的排列
  • 19216811122共有11位数字，划分为4段，每段数值的位数的排列：[2, 3, 3, 3], [3, 2, 3, 3], [3, 3, 2, 3], [3, 3, 3, 2]

  • 对应的IP：[19.216.811.122], [192.16.811.122], [192.168.11.122],

    [192.168.111.22]

• 排除掉数值>255的IP地址
  • 因811 > 255，排除掉[19.216.811.122], [192.16.811.122]
  • 剩下[192.168.11.122], [192.168.111.22]

    

题解

采用回溯算法来实现

public class IpAddresses {
  // IPV4共分4段
  int group = 4;

  /**
   * 还原IP
   *
   * @param s
   * @return
   */
  public List<String> restore(String s) {
    List<List<Integer>> permList = new ArrayList<>();
    // 计算每段数值的位数的排列
    permutation(permList, new ArrayList<>(), s.length());
    List<String> res = new ArrayList<>();
    // 按照计算出来的排列还原IP
    handleIP(s, permList, res);
    return res;
  }

  /**
   * 根据数值的位数的排列，还原IP
   *
   * @param s
   * @param permList
   * @param res
   */
  private void handleIP(String s, List<List<Integer>> permList, List<String> res) {
    for (List<Integer> list : permList) {
      int index = 0;
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < list.size(); i++) {
        String sTmp = s.substring(index, index += list.get(i));
        // 排除数值以"0"开头的无效IP
        if (sTmp.length() > 1 && sTmp.startsWith("0")) break;
        // 排除数值>255的无效IP
        if (Integer.valueOf(sTmp) > 255) break;
        sb.append(Integer.valueOf(sTmp));
        if (i < list.size() - 1) sb.append(".");
        else res.add(sb.toString());
      }
    }
  }

  /**
   * "回溯"，计算数值的位数的排列
   *
   * @param res
   * @param list
   * @param length
   */
  private void permutation(List<List<Integer>> res, List<Integer> list, int length) {
    if (list.size() > group || length < 0) return;
    if (list.size() == group && length == 0) {
      res.add(new ArrayList<>(list));
      return;
    }
    for (int i = 1; i < group; i++) {
      list.add(i);
      permutation(res, list, length - i);
      list.remove(list.size() - 1);
    }
  }

  public static void main(String[] args) {
    IpAddresses ipAddresses = new IpAddresses();
    String s = "19216811122";
    System.out.println(ipAddresses.restore(s));
  }
}
           

总结

本题被包装成一个还原IP的问题，经分析可转化为求解4个数字的排列问题。找到了问题的本质，往往就找到了解题的思路