Simplify Path Solution


  • 0
    C

    Approach #1 Using Stack [Accepted]
    Very straight forward approach. First, split the path into an array of string. Then create a stack to maintain directory levels, loop through each string, "." means skip, ".." means pop, others should be pushed into the stack.
    At last, what left in the stack is the sequence of the simplified path.
    Here's the code.

    String[] p = path.split("/");
            Deque<String> q = new LinkedList<String>();
            for(String dir : p){
                if("..".equals(dir)){
                    if(!q.isEmpty())
                        q.pop();
                }else if(".".equals(dir) || "".equals(dir))
                    continue;
                else
                    q.push(dir);
            }
            if(q.size() == 0) return "/";
            StringBuilder sb = new StringBuilder();
            for(String dir : q){
                sb.insert(0, dir);
                sb.insert(0, "/");
            }
            return sb.toString();
    

    Complexity Analysis

    • Time complexity: O(n).
    • Space complexity: O(n). A string array and a stack are used, each takes O(n) space.

    Approach #2 Two Pointers From Tail [Accepted]
    Using two pointers to start from tail:
    A valid pointer to maintain where the simplified path starts from.
    An index pointer to find next directory in the simplified path.
    This approach is much faster than Approach #1.
    Here's the code.

        public String simplifyPath(String path) {
            char[] arr = path.toCharArray();
            int len = arr.length, valid = len - 1, skip = 0, i, back;
            if (arr[len - 1] == '/') {
                i = len - 2;
                back = len - 1;
            } else {
                i = len - 1;
                back = len;
            }
            // search for first valid directory (skip "..", "." and ""
            while (i >= 0) {
                while (i >= 0 && arr[i] != '/') i--; // find next "/"
                if ((back - i == 2 && arr[back - 1] == '.') || back - i == 1) {
                    back = i;
                } else if (back - i == 3 && arr[back - 1] == '.' && arr[back - 2] == '.') {
                    skip++;
                    back = i;
                } else {
                    i = back - 1;
                    break;
                }
            }
    
            if (i < 0) return "/";
    
            while (i >= 0) {
                while (i >= 0 && arr[i] != '/') i--;
                if ((back - i == 2 && arr[back - 1] == '.') || back - i == 1) {
                    back = i;
                    i--;
                } else if (back - i == 3 && arr[back - 1] == '.' && arr[back - 2] == '.') {
                    skip++;
                    back = i;
                    i--;
                } else {
                    if (skip > 0) {
                        skip--;
                    } else {
                        back--;
                        while (back >= i) {
                            arr[valid--] = arr[back--];
                        }
                    }
                    back = i;
                    i--;
                }
            }
            if (valid == len - 1) return "/";
            return String.valueOf(arr, valid + 1, len - valid - 1);
    

    Complexity Analysis

    • Time complexity : O(n). Only one loop over char array, i and valid each travels at most one time through char array. However, in stack approach, string compare and copy operation are very consuming. So this approach is much faster, and beats over 99% of java submission.
    • Space complexity : O(n). An array of char is used to store original path.

Log in to reply
 

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