leetcode刷题（71）——93. 复原IP地址

class Solution {
   public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        List<String> menber = new ArrayList<>();
        backtrace(s, 0, menber, res);
        return res;
    }

    // depth控制递归深度
    public void backtrace(String s, int index, List<String> men, List<String> res) {
        if (men.size() == 4) {
            if (index == s.length()) {
                // 如果字符串都取完了，可以加入结果集
                res.add(String.join(".", men));
            }
            return;
        }
        // 每组ip地址的长度，最大为3
        for (int i = 1; i <= 3; i++) {
            if (index + i > s.length()) break;
            // 注意ip数字的合法性，不能大于255
            String substring = s.substring(index, index + i);
            if (Integer.parseInt(substring) > 255) break;
            int num = Integer.parseInt(substring);
            // 不能存在01.001.01.01
            if (String.valueOf(num).length() != i) break;
            men.add(substring);
            backtrace(s, index + i, men, res);
            //这里不能直接使用remove,因为如果存在相同值多个，例如多个1，会从前向后移除，产生错误结果，所以应该从后往前移除
            men.remove(men.lastIndexOf(substring));
        }
    }
}

        // 不能存在01.001.01.01
       if (String.valueOf(num).length() != i) break;

men.add(substring);
            backtrace(s, index + i, men, res);
            //这里不能直接使用remove,因为如果存在相同值多个，例如多个1，会从前向后移除，产生错误结果，所以应该从后往前移除
            men.remove(men.lastIndexOf(substring));