[leetcode] 71. 简化路径-解题方法

我们将path'/'作为分隔符,将'/'之间的字符串str加入到栈中。由于str存在''...几种特殊字符串。所以需要按以下方式处理:

  • str = ""时,str不加入栈。
  • str = "."时,str不加入栈。
  • str = ".."时,栈顶有元素则栈顶元素出栈,否则不进行处理。
  • str等于其他字符串时,str加入栈。

最后我们依次将栈顶元素出栈,出栈的str加入到规范路径末尾,出栈结束即可求得规范路径

java代码

public String simplifyPath(String path) {
    int i = 0;
    String str = "";
    Stack<String> stack = new Stack<>();
    while (i < path.length()) {
        if (path.charAt(i) == '/') {
            if (str.equals(".") || str.equals("")) {

            } else if (str.equals("..")) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                // 每个入栈的字符串前面加上'/',方便后续简化路径的处理
                stack.push("/" + str);
            }
            str = "";
        } else {
            str += path.charAt(i);
        }
        i++;
    }
    // path最后一个字符不为'/'时,最后的str需要单独处理
    if (str.equals(".") || str.equals("")) {

    } else if (str.equals("..")) {
        if (!stack.isEmpty()) {
            stack.pop();
        }
    } else {
        stack.push("/" + str);
    }
    StringBuilder builder = new StringBuilder();
    while (!stack.isEmpty()) {
        builder.insert(0, stack.pop());
    }
    // 当简化路径为空时,返回根目录'/'
    return builder.toString().equals("") ? "/" : builder.toString();
}

复杂度分析

  • 时间复杂度: O ( N ) O(N) O(N),需要遍历一次path N N Npath长度。
  • 空间复杂度: O ( N ) O(N) O(N),需要提供栈存储path分割后的字符串,还需要返回结果字符串。

  • 个人小游戏
    个人小游戏
    在这里插入图片描述
上一篇:Git的相关使用(工作常用)


下一篇:Vue 技术进阶 day2 数据监视的原理、其他内置指令、自定义指令、生命周期、组件化、VueComponent构造函数