93. Restore IP Addresses

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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 “[email protected]” are invalid IP addresses.

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"]

Code

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

        helper(s, res, 0, 4, "");
        return res;
    }

    private void helper(String s, List<String> res, int index, int remain, String curr){
        if(remain == 0){
            if(index == s.length()){
                res.add(curr);
            }

            return;
        }

        for(int i = 1; i <= 3; i++){
            if(index + i > s.length()) break;
            if(i != 1 && s.charAt(index) == '0' ) break;

            String temp = s.substring(index, index + i);
            int val = Integer.valueOf(temp);

            if(val <= 255){
                helper(s, res, index + i, remain - 1, curr + temp + (remain == 1 ? "" : "."));
            }
        }
    }
}