位元組跳動面試算法題——還原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個數字的排列問題。找到了問題的本質，往往就找到了解題的思路