93. Restore IP Addresses

Leetcode String Backtracking

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

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

分析

要求根据给定字符串，返回有效的IP地址。使用回溯法是非常显而易见的。但是这道题目有几个trick：

1. 每个点号分隔的区间表示的数字在0～255之间，然而像012这样的数字是错误的，不能在前面有0。如果允许的话，12和012是重复的，ip地址不唯一。
2. 为了表示ip地址，只需要记录下点号的位置即可，如果将原字符串频繁的插入、删除点号，那么每次插入和删除的最坏时间复杂度将会是$O(n)$，其中$n$是字符串长度，显然是不实际的。
3. 确认剩下的字符串长度能够有效表示ip地址，可以加快回溯。

private List<String> ipAddresses;
public List<String> restoreIpAddresses(String s) {
    ipAddresses = new ArrayList<>();
    LinkedList<Integer> dotPosition = new LinkedList<>();
    restoreIpAddressesHelper(s, dotPosition, 0);
    return ipAddresses;
}

private void restoreIpAddressesHelper(String s, LinkedList<Integer> dotPosition, int sep){
    // check if have valid solution: remaining length is larger than capacity
    if ((4 - dotPosition.size()) * 3 < s.length() - sep) return;

    // base case
    if (dotPosition.size() == 3 && validSubIP(s, sep, s.length())) {
        StringBuilder sb = new StringBuilder(s);
        for (int i = 0; i < 3; i++) sb.insert(dotPosition.get(i) + i, ".");
        ipAddresses.add(sb.toString());
        return;
    }

    for (int i = 1; i <= 3; i++)
        if (validSubIP(s, sep, sep + i)) {
            dotPosition.addLast(sep + i);
            restoreIpAddressesHelper(s, dotPosition, sep + i);
            dotPosition.removeLast();
        }
}

// check if a part of ip address is valid: in the range of 0 ~ 255
private boolean validSubIP(String s, int start, int end) {
    // check if start, end is in the range of (0, s.length())
    if (start < 0 || end > s.length()) return false;
    // check length
    int len = end - start;
    if ( len <= 0 || len > 3) return false;
    // check any leading 0: for example 015 is invalid
    if (len > 1 && s.charAt(start) == '0') return false;
    if (len < 3) return true;
    return s.substring(start, end).compareTo("256") < 0;
}