Very simple constant space-time iterative solution (no backtracking, no recursion)


  • 0
    T
    public List<String> restoreIpAddresses(String input) {
        if (input == null || input.length() < 4) return Collections.emptyList();
        List<String> result = new ArrayList<>();
        char[] s = input.toCharArray();
        final int dot0 = 0, dot4 = s.length; // just to make usages look similar
        // Split s into dot0 <ip-part> dot1 <ip-part> dot2 <ip-part> dot3 <ip-part> dot4
        // didn't indent for loops to prevent deep control structures and align code
        for (int dot1 = dot0 + 1; dot1 <= dot0 + 3 && isValid(s, dot0, dot1); ++dot1)
        for (int dot2 = dot1 + 1; dot2 <= dot1 + 3 && isValid(s, dot1, dot2); ++dot2)
        for (int dot3 = dot2 + 1; dot3 <= dot2 + 3 && isValid(s, dot2, dot3); ++dot3)
            if (isValid(s, dot3, dot4)) { // // validate if 4th part is valid
                result.add(new StringBuilder()
                    .append(s, dot0, dot1 - dot0)
                    .append('.')
                    .append(s, dot1, dot2 - dot1)
                    .append('.')
                    .append(s, dot2, dot3 - dot2)
                    .append('.')
                    .append(s, dot3, dot4 - dot3)
                    .toString()
                );
            }
        return result;
    }
    
    /* from inclusive, to exclusive */
    boolean isValid(char[] s, int from, int to) {
        if (s.length < to) return false;
        int len = to - from;
        if (len <= 0 || 3 < len) return false; // to short or long to be an IP part
    
        int num = 0;
        for (int i = from; i < to; ++i) {
            if (num == 0 && from < i) return false; // number starts with 0, but equal to "0"
            num = num * 10 + (s[i] - '0');
        }
        return 0 <= num && num <= 255; // so far only checked for 1-3 length, which includes 999
    }

Log in to reply
 

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