[LeetCode] 71. Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

• Did you consider the case where path = "/../"?
  In this case, you should return "/".
• Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
  In this case, you should ignore redundant slashes and return "/home/foo".

Thought process:

Use stack. Split the string by '/'. Iterate through the elements. There are several cases:

1. Word: push onto stack.
2. '.': ignore.
3. '..': pop the top element from stack.
4. Empty string: two '/' together. Ignore.

At the end, concatenate the words to a StringBuilder and reverse it. Push a '/' onto stack at the beginning so that the returned path will have a '/' at the beginning and the edge case "/../" can be covered.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

class Solution { public String simplifyPath(String path) { String[] items = path.split("/"); Stack<String> stack = new Stack<>(); for (String item : items) { if (item.length() == 0 || item.equals(".")) { continue; } if (item.equals("..")) { if (!stack.isEmpty()) { stack.pop(); } } else { stack.push(item); } } Stack<String> reversed = new Stack<>(); while (!stack.isEmpty()) { reversed.push(stack.pop()); } StringBuilder sb = new StringBuilder(); while (!reversed.isEmpty()) { sb.append('/'); sb.append(reversed.pop()); } return sb.length() == 0 ? "/" : sb.toString(); } }

Time complexity: O(n) where n = path.length.