93 Restore IP Addresses

93. Restore IP Addresses

1. Question

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example: Given"25525511135",

return["255.255.11.135", "255.255.111.35"]. (Order does not matter)

2. Implementation

(1) Backtracking

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();

        if (s == null || s.length() == 0) {
            return res;
        }

        List<String> parts = new ArrayList<>();
        getIpAddresses(s, 0, parts, res);
        return res;
    }

    public void getIpAddresses(String s, int start, List<String> parts, List<String> res) {
        if (start == s.length() && parts.size() == 4) {
            res.add(parts.get(0) + "." + parts.get(1) + "." + parts.get(2) + "." + parts.get(3));
            return;
        }

        // ip地址由4部分组成，每个部分有1-3个数位组成，4 - parts.size()表示我们需要的ip地址剩余的部分，s.length() - start表示目前string剩下的长度
        // 以下两种情况我们会停止搜索
        // 1. 如果ip地址每个部分由1个数位组成，那么我们需要的ip地址剩余的部分至少为4 - parts.size(), 如果4 - parts.size()大于string剩下的长度，说明string剩余的长度无法构成由1个数位组成4个部分的ip地址
        // 2. 如果ip地址每个部分由3个数位组成，那么我们需要的ip地址剩余部分最多为3 * (4 - parts.size()), 如果3 * (4 - parts.size())小于剩余string剩下的长度，说明string无法完全用来构成ip地址
        if (4 - parts.size() > s.length() - start || 4 - parts.size() < (s.length() - start) / 3) {
            return;
        }

        for (int i = start; i < start + 3 && i < s.length(); i++) {
            String part = s.substring(start, i + 1);

            if (isValid(part)) {
                parts.add(part);
                getIpAddresses(s, i + 1, parts, res);
                parts.remove(parts.size() - 1);
            }
        }
    }

    public boolean isValid(String s) {
        if (s.startsWith("0") && s.length() > 1) {
            return false;
        }
        int num = Integer.parseInt(s);
        return num >= 0 && num <= 255;
    }
}

3. Time & Space Complexity

Backtracking： 时间复杂度O() ?, 空间复杂度O() ?