【CodeTop 03】2024-08-02 - 93. 复原 IP 地址

[larscheng]

93. 复原 IP 地址

[larscheng]

思路

回溯，dfs遍历所有可能的分割方法，同时剪枝错误的分割方式 图解

代码

class Solution {
      //收集ip地址
      List<String> result = new ArrayList<>();
      //收集分段ip数字
      LinkedList<String> segment = new LinkedList<>();

    public List<String> restoreIpAddresses(String s) {
        dfs(s,0);
        return result;
    }

    private void dfs(String str, int start) {
        //结束条件
        if (start == str.length() && segment.size() == 4) {
            result.add(String.join(".", segment));
            return;
        }
        //剪枝1，已经收集够4分段，但是字符串还有剩余
        if (segment.size()==4&&start< str.length()){
            return;
        }
        //3中分割步长，1、12、123
        for (int i = 1; i <= 3; i++) {
            //剪枝2，分割右边界越界
            if (start + i > str.length()) {
                return;
            }
            //剪枝3，出现0x、0xx
            if (i>1&& str.charAt(start)=='0'){
                return;
            }
            String substring = str.substring(start, start + i);

            //剪枝4，3位数大于255
            if (i==3 && Integer.parseInt(substring)>255){
                return;
            }
            segment.add(substring);

            dfs(str, start + i);

            segment.removeLast();
        }
    }
}

复杂度

• 时间复杂度：todo
• 空间复杂度：O(len)，len是ip段数，实际为4