# 0093. Restore IP Addresses

https://leetcode.com/problems/restore-ip-addresses

## Description

Given a string `s` containing only digits, return all possible valid IP addresses that can be obtained from `s`. You can return them in **any** order.

A **valid IP address** consists of exactly four integers, each integer is between `0` and `255`, separated by single dots and cannot have leading zeros. For example, "0.1.2.201" and "192.168.1.1" are **valid** IP addresses and "0.011.255.245", "192.168.1.312" and "192.168@1.1" are **invalid** IP addresses.&#x20;

**Example 1:**

```
**Input:** s = "25525511135"
**Output:** ["255.255.11.135","255.255.111.35"]
```

**Example 2:**

```
**Input:** s = "0000"
**Output:** ["0.0.0.0"]
```

**Example 3:**

```
**Input:** s = "1111"
**Output:** ["1.1.1.1"]
```

**Example 4:**

```
**Input:** s = "010010"
**Output:** ["0.10.0.10","0.100.1.0"]
```

**Example 5:**

```
**Input:** s = "101023"
**Output:** ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
```

**Constraints:**

* `0 <= s.length <= 3000`
* `s` consists of digits only.

## ac

```java
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        // Edge cases
        if (s == null || s.length() < 4) {
            return res;
        }

        restore(0, s, new ArrayList<>(), res);

        return res;
    }

    private void restore(int start, String s, List<Integer> note, List<String> res) {
        if (note.size() == 4) {
            if (start == s.length()) {
                res.add(note.stream().map(String::valueOf).collect(Collectors.joining(".")));
            }
            return;
        }

        for (int i = 1; i < 4 && start + i <= s.length(); i++) {
            String tmp = s.substring(start, start + i);
            if (tmp.startsWith("0") && tmp.length() > 1) continue;
            int num =  Integer.parseInt(tmp);
            if (num > 255) continue;

            note.add(num);
            restore(start + i, s, note, res);
            note.remove(note.size() - 1);
        }
    }
}
```
