Java recursive simple code with comments


  • 1
    public class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> list = new ArrayList<>();
            if (s == null || s.length() < 4 || s.length() > 12)
                return list;
            restoreIpAddresses(list, "", 0, s, 0);
            return list;
        }
        
        private void restoreIpAddresses(List<String> list, String ip, int i, String s, int j) {
            if (i == 4) {
                if (j == s.length()) {
                    ip = ip.substring(0, ip.length() - 1); // remove the last "."
                    list.add(ip);
                }
                return; // whole ip is restored but s has leftover: fail
            }
            if (i < 4 && j == s.length()) // ip is not done but s has no leftover: fail
                return;
            restoreIpAddresses(list, ip + s.substring(j, j + 1) + ".", i + 1, s, j + 1); // 1 digit
            if (j + 1 < s.length() && s.charAt(j) != '0')
                restoreIpAddresses(list, ip + s.substring(j, j + 2) + ".", i + 1, s, j + 2); // 2 digits
            if (j + 2 < s.length() && s.charAt(j) != '0' && Integer. parseInt(s.substring(j, j + 3)) < 256) // 3 digits
                restoreIpAddresses(list, ip + s.substring(j, j + 3) + ".", i + 1, s, j + 3);
        }
    }

Log in to reply
 

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