JAVA Solution Beat 100% Users


  • 0
    C
    public class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> result = new ArrayList<>();
            if (s == null || s.length() < 4 || s.length() > 12) {
                return result;
            }
            char[] array = s.toCharArray();
            char[] path = new char[s.length() + 3];
            int num = 0;
            for (int i = 0; i < 3; i++) {
                num = 10 * num + array[i] - '0';
                if (num > 255) {
                    break;
                }
                path[i] = array[i];
                dfs(result, path, array, i + 1, i + 1, 0);
                // we could not let 0 to be the prefix of a positive number
                if (num == 0) {
                    break;
                }
            }
            return result;
        }
        
        private void dfs(List<String> result, char[] path, char[] array, int index, int length, int dot) {
            if (dot == 3) {
                if (index == array.length) {
                    result.add(new String(path));
                }
                return;
            }
            path[length] = '.';
            int num = 0;
            for (int i = index; i < Math.min(index + 3, array.length); i++) {
                num = 10 * num + array[i] - '0';
                if (num > 255) {
                    break;
                }
                path[length + 1 + i - index] = array[i];
                dfs(result, path, array, i + 1, length + 2 + i - index, dot + 1);
                if (num == 0) {
                    break;
                }
            }
        }
    }
    

    Maybe this solution will be beaten in the future because of more excellent solution, but by the time I submitted it is still a good solution.

    Since the digits can only between 4 to 12, I excluded the other length. And then at first I iterate either the first three digits of the string or three digits after a dot, and at the position of every digits, I can do dfs again. But when the first digit at the beginning or right after a dot is 0, we could not do dfs because the prefix of a positive number can not be 0. Another condition is that after iterating three digits, the value is larger than 255, it is illegal value in IP{ address, so we terminate the iteration without doing deeper dfs.

    I think this is my thoughts for the problem. Please feel free to question since the explanation may not be clear enough or maybe there are extreme test cases that will fail this solution.

    Parameters in the dfs method signature
    array: I just converted num to a character array
    path; the current IP address stored inside
    index: the index of the current digits in the digit array
    length: current length of the path array we have already filled characters
    dot: number of dots we have currently


Log in to reply
 

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