Tag Archives: String Buffer

Path simplify

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

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

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".

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

Well it’s not difficult, but there are something worth noting. The examples above should also tell us that the path may or may not end with ‘/’. So be sure to deal with cases like /abc/…

So when we are evaluating the path ourselves,  we do in the following way (e.g., ‘/a/./b/../../c/’)

  1. ‘a’ means /a
  2. ‘.’ means we stay on the current level, so still ‘/a’
  3. ‘b’ leads to ‘/a/b’
  4. ‘..’ means we have to go up, so we get ‘/a’ again
  5. ‘..’ the same as above, so we get ‘/’
  6. ‘c’ leads to ‘/c’
  7. There is no more, so we end with ‘/c’

I don’t know if you notice anything here but I was reading about data structures for a while and one thing that caught my eyes was the string ‘..’ and its effect on the final path. If the string between two ‘/’ are not empty string, ‘.’ or ‘..’, we are adding them to the end of the final path. If it is ‘..’, we are removing it from the path. Well this sounds like push and pop operation to me. That’s it. Nothing fancy.

We will scan through the input and look for the strings (I used a StringBuilder here and be sure to initialize a new one for the new string you are trying to find here, otherwise the former string is still in the builder and you will get bugs) between two ‘/’s and push/pop them to/from the stack based on their values. Once the scan is completed, we can move the items in the stack to an array and use a StringBuilder to create the final path.

Code on github:

Enhanced by Zemanta