回溯——93.复原IP地址

之前的回溯都是,回溯树的深度是不确定的,这次的回溯深度是确定的——4,这次的结束判定是:

  1. 深度为4
  2. 遍历到最后一个数字
    private void backtracking(String[] partition, int startInde) {
        StringBuilder sb = new StringBuilder("");
        for (int i = startIndex; i <= startIndex+3 && i < partition.length; ++i) {
            sb.append(partition[i]);
            //每个整数位于 0 到 255 之间组成
            if (Integer.valueOf(sb.toString()) <= 255) {
                path.add(sb.toString());
                //有效地址的判定条件:
                //1 深度为4
                //2 遍历到最后一个数字
                if (i == partition.length-1 && path.size() == 4) {
                    StringBuilder ans = new StringBuilder();
                    //这些地址可以通过在 s 中插入 '.' 来形成
                    for (String s : path) {
                        ans.append("." + s);
                    }
                    result.add(ans.substring(1));
                } else {
                    backtracking(partition, i+1);
                }
                path.remove(path.size()-1);
            }
            //且不能含有前导 0
            if (sb.toString().equals("0")) {
                break;
            }
        }
    }

 

上一篇:回溯


下一篇:77. 组合