Simplify Path, Leetcode 解题笔记

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

这题目描述的不明确,很多corner case想不到,比如按照例子中的理解,path的最后没有‘/’来结尾好像应该是invalid的输入,但是test case里面出现了这种情况:
Input: “/…”
Output: “/”
Expected: “/…”

自己写的code没通过上面的case,懒得改了,看网上有一种很简洁的写法:
利用栈的特性,如果sub string
1. 等于“.”或者空,什么都不需要干,直接开始寻找下一个substring
2. 等于“..”,弹出栈顶元素,寻找下一个substring
3. 等于其他,插入当前substring为新的栈顶,寻找下一个substring

注意第10行的split用法非常简洁,值得借鉴。

public class Solution {
   public String simplifyPath(String path) {
       
       StringBuilder result=new StringBuilder();
        
       if (path==null ||path.length()==0){
           return result.toString();
       }
       
       String[] strs=path.split("/");
       
       Stack<String> stack=new Stack<String>();
 
       for (String s: strs){
           
           if (s.length()==0 ||s.equals(".")){
               
           }
           else if (s.equals("..")){
               if (!stack.isEmpty()){
                   stack.pop();
               }
           }
           else{
               stack.push(s);
           }
           
       }
       
       if (stack.isEmpty()){
           result.append('/');
           
       }
       else{
           
           while (!stack.isEmpty()){
               result.insert(0, stack.pop());
               result.insert(0, '/');
           }
       }
       
       return result.toString();
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s