[leetcode]Simplify Path

新博文地址：[leetcode]Simplify Path

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，所以压根就不明白那些/.和/..是啥东西。好吧，原来是这样的

/.表示当前目录，/..表示上级目录，/表示根目录

 

/a/./b/../../c/为例，

 

/a表示进入a目录，/.表示当前目录，即还是a目录，因此可以无视

 

/b表示进入b目录，当前的目录为/a/b

 

/..表示返回上级目录，即回到了/a

 

同理，再返回一次，就回到的根目录/

 

然后进入c目录，最后的目录结构为：/c

 

tip中给了两点，根目录的上级目录还是根目录，斜线/可能有蛋疼的多条，比如//a、///a其实与/a的效果是一样的。

 

 

 

我的思路比较单纯：

 

 

 

	public String simplifyPath(String path) {
		if(path == null || path.length() == 0){
			return null;
		}
		while(!path.trim().replaceAll("//", "/").equals(path)){//如果有多条斜线"/"，全部替换成单条"/"
			path = path.trim().replaceAll("//", "/");
		}
		if(path.charAt(path.length() - 1) != '/'){//如果目录最后不是以"/"结尾的，人工的添加上
			path += "/";
		}
		StringBuilder simplifyPath = new StringBuilder();
		Stack<String> stack = new Stack<String>();
		int[] slash = new int[path.length()];//存储每个"/"在path中的下标
		int slashIndex = 0;
		for(int i = 0; i < path.length();i++){
			if(path.charAt(i) == '/'){
				slash[slashIndex++] = i;
			}
		}
		for(int i = 1; i < slashIndex;i++){
			String tem = path.substring(slash[i-1] + 1, slash[i]);//每两个"/"之间的字符串即是一级目录
			if(!".".equals(tem) && !"..".equals(tem)){//正常的目录，则压栈
				stack.push(tem);
			}else if("..".equals(tem)){//遇到返回，则弹栈
				if(!stack.isEmpty()){//if stack is empty ,do nothing
					stack.pop();
				}
			}
		}
		while(!stack.isEmpty()){
			String tem = stack.pop();
			simplifyPath.insert(0, "/"+ tem);
		}
		return simplifyPath.toString().isEmpty() ? "/" :simplifyPath.toString();
	}