My backtracking Java implementation


  • 0
    A
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        if (s == null || s.length() == 0) return result;
        String[] address = new String[4];
        restore(s.toCharArray(), 0, 0, address, result);
        return result;
    }
    
    private void restore(char[] s, int i, int level, String[] address, List<String> result) {
        if (i == s.length && level == 4) result.add(convertToIPAddress(address));
        if (i == s.length || level == 4) return; //invalid parsing
        for (int c = 1; c <= 3; c++) {
            if (i + c > s.length) break; //out of bound
            String ip = String.valueOf(s, i, c);
            if (isValidIP(ip)) {
                address[level] = ip;
                restore(s, i + c, level + 1, address, result);
            }
        }
    }
    
    private boolean isValidIP(String s) {
        if (s.length() > 1 && s.charAt(0) == '0') return false;
        return Integer.valueOf(s) < 256;
    }
    
    private String convertToIPAddress(String[] address) {
        StringBuilder sb = new StringBuilder();
        boolean first = true;
        for (String s : address) {
            if (first) first = false;
            else sb.append('.');
            sb.append(s);
        }
        return sb.toString();
    }

Log in to reply
 

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