Sunday, January 11, 2015

Simplify Path (LeetCode String)

Question: Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

Idea: First split the input string by "/+", then the dirs are stored in a string array. Scan the array from left to right and add the dirs to a arraylist, if ".." (goes up one level) shows up, delete the last dir to go up one level.  At the end, remove the last "/" is the intended output is not "/".

Time: O(n) Space: O(n)

Code:
 public class Solution {  
   public String simplifyPath(String path) {  
     StringBuilder result=new StringBuilder("/");  
     String[] cols=path.split("/+");  
     ArrayList<String> dirs=new ArrayList<String>();  
     for(String s:cols)  
     {  
       if(s.equals(".."))  
       {  
         if(dirs.isEmpty()==false)  
           dirs.remove(dirs.size()-1);  
       }  
       else if(!s.equals(".")&&!s.equals(""))  
       {  
         dirs.add(s);  
       }  
     }  
     for(String dir:dirs)  
     {  
       result.append(dir);  
       result.append("/");  
     }  
     if(result.length()>1)  
       result.deleteCharAt(result.length()-1);  
     return result.toString();  
   }  
 }  

No comments:

Post a Comment