Java DFS


  • 0
    M
        public List<String> restoreIpAddresses(String s) {
            List<String> ips = new ArrayList<>();
            restore(s, 0, 0, new StringBuilder(), ips);
            return ips;
        }
        private void restore(String s, int st, int ipInd, StringBuilder ip, List<String> ips) {
            if (ipInd == 4) {
                if (st == s.length()) {
                    ips.add(ip.toString());                
                }
                return;
            }
            int n = s.length();
            int preLen = ip.length();
            for (int i = st; i < Math.min(st + 3, n - (3 - ipInd)); ++i) {
                String substr = s.substring(st, i + 1);
                try {
                    int num = Integer.parseInt(substr);
                    if (num >= 0 && num < 256) {
                        if (ipInd > 0) ip.append('.');
                        ip.append(substr);
                        restore(s, i + 1, ipInd + 1, ip, ips);
                        ip.setLength(preLen);
                    }
                } catch (NumberFormatException excp) {
                    break;
                }
                if (s.charAt(st) == '0') {
                    break;
                }
            }
        }
    

Log in to reply
 

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