Java simplest O(n) solution without using a stack. 9ms, beats 80%.


  • 0
    Y

    The idea is very simple. Instead of reading string sequence from the beginning, I initialize the pointer to point the end of the string sequence, so it reads in reverse order. Whenever we encounter a "..", we increment the counter by 1, which counts the number of folder levels we should ignore when we reads back. And when the counter hits 0, it means this folder should appear in our final result.

    public String simplifyPath(String path) {
            String[] arr = path.split("/");
            StringBuilder sb = new StringBuilder();
            int p = arr.length - 1, count = 0;
            while (p >= 0) {
                if (arr[p].equals(".."))
                    count++;
                else if (!arr[p].equals(".") && !arr[p].equals("")) {
                    if (count > 0)
                        count--;
                    else sb.insert(0, "/" + arr[p]);
                }
                p--;
            }
            return sb.length() == 0? "/": sb.toString();
        }

Log in to reply
 

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