LeetCode 93:复原 IP 地址

题目

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：
输入：s = "0000"
输出：["0.0.0.0"]

示例 3：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

思路

此题类似分割字符串问题，可以利用回溯法把所有可能结果搜索出来。回溯法首先应确定递归参数，每次不能搜索重复的部分，因此要有startIndex，同时题目要求分为4段，因此需要一个参数记录目前分割了多少段，也就是递归终止条件，当分成四段时候将字符串加入结果集，同时结果还需要合法，因此需要一个函数来判断是否截取子串是否合法，每个子串都要判断。在单层递归逻辑中，[startIndex, i] 这个区间就是截取的子串

代码

class Solution {
    List<String> res=new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        
        backracking(s,0,0);
        return res;
    }
    public boolean isValid(String s,int start,int end)
    {
        if (start > end) {
            return false;
        }
        if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果⼤于255了不合法
                return false;
            }
        }
        return true;

    }
    public void backracking(String s,int startIndex,int split)
    {
        if(split==3)
        {
            if(isValid(s,startIndex,s.length()-1))
            {
                res.add(s);
            }
            else
            return;
        }
        for(int i=startIndex;i<s.length();i++)
        {
            if(isValid(s,startIndex,i))
            {
                s=s.substring(0, i + 1) + "." + s.substring(i + 1);
                split++;
                backracking(s,i+2,split);//跳过加入的逗点
                split--;
                s=s.substring(0, i + 1) + s.substring(i + 2);// 回溯删掉逗点
            }
            else//不合法直接跳出循环回到上一步
            break;
        }
    }
}

反思

①优化：可以进行剪枝

class Solution {
    List<String> result = new ArrayList<String>();
	StringBuilder stringBuilder = new StringBuilder();

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

	// number表示stringbuilder中ip段的数量
	public void restoreIpAddressesHandler(String s, int start, int number) {
		// 如果start等于s的长度并且ip段的数量是4，则加入结果集，并返回
		if (start == s.length() && number == 4) {
			result.add(stringBuilder.toString());
			return;
		}
		// 如果start等于s的长度但是ip段的数量不为4，或者ip段的数量为4但是start小于s的长度，则直接返回
		if (start == s.length() || number == 4) {
			return;
		}
		// 剪枝：ip段的长度最大是3，并且ip段处于[0,255]
		for (int i = start; i < s.length() && i - start < 3 && Integer.parseInt(s.substring(start, i + 1)) >= 0
				&& Integer.parseInt(s.substring(start, i + 1)) <= 255; i++) {
			// 如果ip段的长度大于1，并且第一位为0的话，continue
			if (i + 1 - start > 1 && s.charAt(start) - '0' == 0) {
				continue;
			}
			stringBuilder.append(s.substring(start, i + 1));
			// 当stringBuilder里的网段数量小于3时，才会加点；如果等于3，说明已经有3段了，最后一段不需要再加点
			if (number < 3) {
				stringBuilder.append(".");
			}
			number++;
			restoreIpAddressesHandler(s, i + 1, number);
			number--;
			// 删除当前stringBuilder最后一个网段，注意考虑点的数量的问题
			stringBuilder.delete(start + number, i + number + 2);
		}
	}
}