> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/string/restore-ip-addresses.md).

# Restore IP Addresses

<https://leetcode.com/problems/restore-ip-addresses/description/>

> 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)

## Thoughts

IP地址被三个点分成四块, 每块int值小于256且string不以0开头(除非刚好"0"). 根据这些规则可以用dfs或者循环写.

## Code

```
class Solution {
    /*
    private void helper(String s, int pos, int remains, String cur, List<String> res) {
        if (remains == 0) {
            if (s.length() - pos <= 3) {
                String sub = s.substring(pos);
                int val = Integer.parseInt(sub);
                if (!sub.startsWith("0") && val < 256 || sub.equals("0")) {
                    res.add(cur + "." + s.substring(pos));
                }
            }
            return;
        }
        for (int i = pos; i < pos + 3 && i < s.length() - 1; i++) {
            String sub = s.substring(pos, i + 1);
            int val = Integer.parseInt(sub);
            if (!sub.startsWith("0") && val < 256 || sub.equals("0")) {
                helper(s, i + 1, remains - 1, cur == "" ? sub : cur + "." + sub, res);
            }
        }
    }*/

    private boolean isValid(String sub) {
        if (sub.length() > 3 || sub.length() == 0 ||sub.charAt(0) == '0' && sub.length() > 1 || Integer.parseInt(sub) > 255) {
            return false;
        }
        return true;
    }

    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        int len = s.length();
        for (int i = 0; i < 4 && i < len; i++) {
            for (int j = i + 1; j < i + 4 && j < len; j++) {
                for (int k = j + 1; k < j + 4 && k < len; k++) {
                    String s1 = s.substring(0, i), s2 = s.substring(i, j),
                    s3 = s.substring(j, k), s4 = s.substring(k);
                    if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
                        res.add(s1 + "." + s2 + "." + s3 + "." + s4);
                    }
                }
            }
        }

        //helper(s, 0, 3, "", res);
        return res;
    }
}
```

## Analysis

时间复杂度O(1).