- Difficulty: Medium
Given an absolute path for a file (Unix-style), simplify it.
For example,
path =
path =
path =
"/home/"
, => "/home"
path =
"/a/./b/../../c/"
, => "/c"
思路: split string by '/' into string [] , use a stack to store input.
Notice "a//b" will be splited into "a", ''", "b". When ''(by"//") , "." just skip.
When ".." ,pop stack if not empty
Complexity: O(N)
关键字: Stack(use Deque is better), str.split(''/") into String[]
public class Solution { public String simplifyPath(String path) { Deque<String> deque = new LinkedList<String>(); String[] splits = path.split("/"); for (String split : splits) { if (split.equals("")||split.equals(".")){ continue; }else if (split.equals("..")){ if(!deque.isEmpty())deque.pop(); }else{ deque.push(split); } } StringBuilder builder = new StringBuilder(); while (!deque.isEmpty()) { String s = deque.pop(); builder.insert(0,s); builder.insert(0,"/"); } if (builder.length() == 0) return "/";//edge case: "/../" return "/" return builder.toString(); } }
No comments:
Post a Comment