Very fast JAVA DFS solution beat 97%


  • 0
    Y

    class Solution {

        public List<String> restoreIpAddresses(String s) {
            List<String> results = new LinkedList<>();
            char[] digits = s.toCharArray();
            StringBuilder sb = new StringBuilder();
            getResults(results, sb, digits, 0, 1);
            return results;
        }
        private void getResults(List<String> results, StringBuilder sb, char[] digits, int start, int part) {
            if (part == 4) {
                if(validIP(digits, start, digits.length - 1)) {
                    for (int j = start; j < digits.length; j++) {
                        sb.append(digits[j]);
                    }
                    results.add(sb.toString());
                }
                return;
            }
            for (int i = start; i < digits.length; i++) {
                if (!validIP(digits, start, i) || i >= digits.length + part - 4) {
                    break;
                }
                if (i < digits.length + 3 * (part - 4) - 1) {
                    continue;
                }
                int len = sb.length();
                for (int j = start; j <= i; j++) {
                    sb.append(digits[j]);
                }
                sb.append('.');
                getResults(results, sb, digits, i + 1, part + 1);
                sb.delete(len, sb.length());
            }
        }
        private boolean validIP(char[] digits, int l, int r) {
            
            int address = 0;
            for (int i = l; i <= r; i++) {
                address *= 10;
                address += digits[i] - '0';
            }
            if ((r > l && digits[l] == '0') || address >= 256) {
                return false;
            }
            return true;
        }
    

    }


Log in to reply
 

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