[LeetCode]——简化路径

NO.71 简化路径中等

思路一：栈 现总结一下题目要求的规范路径格式：1.结尾没有/。2.开头必须有/。3每个文件之间只有有且只有一个/。4.’.’直接去掉。5.’..’删去的同时要连带上一个不为空的文件名。

所以本题的主要点在于处理’..’，删去的同时要连带上一个不为空的文件名。这符合栈的后进先出的特性。

将字符串以/分割成数组，得到的可能结果有’’、’.’、’文件’、’..’。

逐一判断，文件名入栈，’..’删去栈顶文件名，最后取出栈内元素拼接。

public String simplifyPath(String path) {
    if (path==null||path.equals(""))return "/";
    //分割
    String[] split = path.split("/");
    Stack<String> stack=new Stack<>();
    //遍历数组，分别判断进行出入栈
    for (int i = 0; i < split.length; i++) {
        if (split[i].equals("..")&&!stack.isEmpty()){
            stack.pop();
        }else if (!split[i].equals("..")&&!split[i].equals("")&&!split[i].equals(".")){
            stack.push(split[i]);
        }
    }
    //栈空
    if (stack.isEmpty())return "/";
    //拼接
    StringBuilder ans=new StringBuilder();
    int size = stack.size();
    for (int i = 0; i < size; i++) {
        ans.append("/").append(stack.get(i));
    }
    return ans.toString();
}

时间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.71 简化路径 中等

NO.71 简化路径中等