Share my concise recursive 3ms Java solution


  • 0
    Y

    Here is my solution:
    We all know that a valid IP address contains four number between 0 and 255, so every time I want to pick up a number, I will check the following points:

    1. the number of remaining numbers.
    2. is this number <= 255
    3. is this number start with 0 but have more than 1 digit.
    class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> res = new ArrayList<>();
            helper(res, s, "", 4);
            return res;
        }
        
        private void helper(List<String> res, String s, String tmp, int digit) {
            if (digit == 1 && Integer.parseInt(s) <= 255 && (s.length() == 1 || s.charAt(0) != '0')) {
                res.add(tmp + s);
                return;
            }
            for (int i = 0; i < 3; i++) {
                if (s.length() - i <= digit * 3 && i + 1 < s.length() && Integer.parseInt(s.substring(0, i + 1)) <= 255 && (i == 0 || s.charAt(0) != '0')) {
                    helper(res, s.substring(i + 1), new String(tmp + s.substring(0, i + 1) + "."), digit - 1);
                }
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.