Simplify Path 421

Question

Given an absolute path for a file (Unix-style), simplify it.

Example

"/home/", => "/home"

"/a/./b/../../c/", => "/c"

Solution

Unix路径简化的依据是：

当遇到“/../"则需要返回上级目录，需检查上级目录是否为空。

当遇到"/./"则表示是本级目录，无需做任何特殊操作。

当遇到"//"则表示是本级目录，无需做任何操作。

当遇到其他字符则表示是文件夹名，无需简化。

当字符串是空或者遇到”/../”，则需要返回一个"/"。

当遇见"/a//b"，则需要简化为"/a/b"。

因此，可以用两个stack来实现。

第一个栈用于保存所有合法的文件夹名。首先将path根据"/"进行划分，对于所有划分出来的字符串，

1. 若等于""（例如"/."划分后就是""和"."）或者"."则什么都不做，

2. 若等于".."则将栈顶元素出栈（相当于返回上级目录，栈为空则什么都不做），

3. 否则入栈（合法文件夹名）。

遍历完所有划分出的字符串后，若栈为空，则返回"/"，否则要按照顺序返回栈中所有文件夹目录名。但是因为是栈，所以栈底元素应该在最前名，所以用第二个栈来将第一个栈中元素取相反顺序后输出。也可以不用第二个stack，直接用string，每次加到最前面，最后将最后一个字符（"/"）删去即可。

代码如下：

public class Solution {
    /**
     * @param path the original path
     * @return the simplified path
     */
    public String simplifyPath(String path) {
        // Write your code here
        if(path == null || path.length() == 0){
            return null;
        }

        String[] array = path.split("/");

        Stack<String> stack = new Stack<String>();
        for(int i = 0; i < array.length; i++){
            if(array[i].equals(".") || array[i].equals("")){
                continue;
            }

            if(array[i].equals("..")){
                if(!stack.isEmpty()){
                    stack.pop();
                }
                continue;
            }

            stack.push(array[i]);
        }

        if(stack.isEmpty()){
            return "/";
        }

        Stack<String> temp = new Stack<String>();
        while(!stack.isEmpty()){
            temp.push(stack.pop());
        }

        String res = "";
        while(!temp.isEmpty()){
            res = res + "/" + temp.pop();
        }

        return res;
    }
}