Java 2ms DFS solution beat 98%


  • 0
    J
        public List<String> restoreIpAddresses(String s) {
            List<String> result = new ArrayList<>();
            restoreIps(new int[4], 0, s, 0, result);
            return result;
        }
        
        void restoreIps(int[] ip, int end, String s, int start, List<String> result) {
            if (end == ip.length && start == s.length()) {
                StringBuilder sb = new StringBuilder();
                sb.append(ip[0]);
                for (int i = 1; i < ip.length; i++) sb.append(".").append(ip[i]);
                result.add(sb.toString());
                return;
            } else if (end == ip.length || start == s.length()) return;
            if (s.charAt(start) == '0') {
                ip[end] = 0;
                restoreIps(ip, end + 1, s, start + 1, result);
            } else {
                int curIp = 0;
                for (int i = start; i < s.length(); i++) {
                    int newIp = curIp * 10 + (s.charAt(i) - '0');
                    if (newIp > 255) return;
                    curIp = newIp;
                    ip[end] = curIp;
                    restoreIps(ip, end + 1, s, i + 1, result);
                }
            }
        }
    

Log in to reply
 

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