[LeetCode] 93. Restore IP Addresses

Posted on | In

Problem

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

Example:

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

Explanation

  1. We can use recursion to solve this problem. We create a helper function that has 4 parameters: input string, result, current string, field. The valid ip address has totoal of 4 fields, for example, field1.field2.field3.field4.

  2. The idea is we first pull out one character from the input string, and check if it’s a valid field, if it is valid field, then we recursivly call the helper function with the updated parameter: updated sub inputString, result, currentString is the character we pull out, field+1. Similarlly, we can pull out two characters to check if it’s a valid field and recursivly call the helper function; we can also pull out three characters and recursivly call the helper function.

  3. We will return if the field is 4 and the string has no length.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    void helper(String s, List<String> res, String cur, int field) {
        if (field == 4 && s.length() == 0) {
            res.add(cur.substring(1));
        } else if (field == 4 || s.length() == 0) {
            return;
        } else {
            helper(s.substring(1), res, cur+"."+s.substring(0, 1), field+1);
            if (s.charAt(0) != '0' && s.length() >= 2) {
                helper(s.substring(2), res, cur+"."+s.substring(0, 2), field+1);
            }
            if (s.charAt(0) != '0' && s.length() >= 3 && Integer.valueOf(s.substring(0, 3)) <= 255) {
                helper(s.substring(3), res, cur+"."+s.substring(0, 3), field+1);
            }
        }
    }

    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if (s == null || s.length() < 4) return res;
        helper(s, res, "", 0);
        return res;
    }
}