A simple, fast and space saving Java DFS solution !


  • 0
    B
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new LinkedList<>();
        if(s == null || s.length() < 4 || s.length() > 12) {
            return result;
        }
        StringBuilder sb = new StringBuilder();
        restoreIpAddresses(s, 0, 0, sb, result, s.length());
        return result;
    }
    private void restoreIpAddresses(String s, int index, int level, StringBuilder sb, List<String> result, int length) {
        int sbL = sb.length();
        if(level == 3) {
            int cur = getValue(s, index, length);
            if(cur >= 0 && cur <= 255) {
                sb.append(cur);
                result.add(sb.toString());
                sb.delete(sbL, sb.length());
            }
            return;
        }
        for(int i = index + 1; i <= index + 3 && i <= length; i++) {
            int cur = getValue(s, index, i);
            if(cur >= 0 && cur <= 255) {
                sb.append(cur);
                sb.append('.');
                restoreIpAddresses(s, i, level + 1, sb, result, length);
                sb.delete(sbL, sb.length());
            }
        }
    }
    private int getValue(String s, int start, int end) {
        if(start >= end) {
            return -1;
        }
        int value = 0;
        for(int i = start; i < end; i++) {
            if(i > start && value == 0) {   // some value like "00", "01" is not valid
                return -1;
            }
            value = value * 10 + Character.getNumericValue(s.charAt(i));
        }
        return value;
    }
    

    DFS will be faster than 3 for loops solution, because we can prune a lot of invalid results.
    In Java, String is immutable. In order to avoid produce too much strings, I choose StringBuilder to store intermedium. The time complexity of string.substring is O(string.length()), and this method will also new a new string, so I use getValue method.


Log in to reply
 

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