算法系列——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”.

程序实现

这道题的要求是简化一个Unix风格下的文件的绝对路径。 字符串处理，由于”..”是返回上级目录（如果是根目录则不处理），因此可以考虑用栈记录路径名，以便于处理。需要注意几个细节： 重复连续出现的’/’，只按1个处理，即跳过重复连续出现的’/’； 如果路径名是”.”，则不处理； 如果路径名是”..”，则需要弹栈，如果栈为空，则不做处理； 如果路径名为其他字符串，入栈。 最后，再逐个取出栈中元素（即已保存的路径名），用’/’分隔并连接起来。

解题思路

public class Solution { public String simplifyPath(String path) { if(path==null||path.length()==0) return null; Stack<String> ss=new Stack<String>(); int i=0; int len=path.length(); while(i<len){ //跳过'/'字符 while(i<len&&path.charAt(i)=='/') i++; //记录字符 String temp=""; while(i<len&&path.charAt(i)!='/') temp+=path.charAt(i++); if("..".equals(temp)&&!ss.isEmpty()) ss.pop(); else if(!"".equals(temp)&&!".".equals(temp)&&!"..".equals(temp)){ ss.push(temp); } } if(ss.isEmpty()) return "/"; StringBuilder sb=new StringBuilder(); for(String str:ss) sb.append("/").append(str); return sb.toString(); }