LeetCode 93. 复原IP地址 题解

思路

本题直接使用回溯法，遍历找出所有可能的IP地址。

重点是边界条件的判断：

// 字符串遍历结束 并且 刚好将字符串分为四组数字 ==> 成功
if (index == s.length() && curString.length() == s.length() + 4) {
    res.add(curString.substring(0,curString.length()-1));
    return;
}
// 字符串遍历结束 或者 字符串分成的组数大于4 
// （“字符串分成的组数大于4 ” 可以通过curString的长度-index得到的就是组数判断，也可以使用列表记录当前的组数来判断）
if (index == s.length() || curString.length() >= index + 4) return;

注意：边界条件不应该只关注字符串的遍历是否结束，还需要判断分组个数是否超过4，否则可能会导致SOF异常。也可以在原字符串长度大于12的时候直接返回空来避免判断分组个数。

代码

import java.util.LinkedList;
import java.util.List;

class Solution {
    List<String> res;
    public List<String> restoreIpAddresses(String s) {
        res = new LinkedList<>();
        if (s.length() > 12){
            return res;
        }
        fun(s, 0, "");
        return res;
    }

    void fun(String s, int index, String curString){
        if (index == s.length() && curString.length() == s.length() + 4) {
            res.add(curString.substring(0,curString.length()-1));
            return;
        }

        if (index >= s.length()) return;

        if (s.charAt(index) == '0'){
            fun(s, index + 1, curString+"0.");
            return;
        }
        // 两位的情况
        for (int i = 0; i < Math.min(2, s.length() - index); i++) {
            fun(s, index + i + 1, curString + s.substring(index, index + i + 1) + ".");
        }
        // index + 3 <= s.length ==> index <= s.length - 3
        if (index <= s.length() - 3){
            int num = Integer.parseInt(s.substring(index, index + 3));
            if (num <= 255){
                fun(s, index + 3, curString + s.substring(index, index + 3) + '.');
            }
        }
    }
}