71. 简化路径

不论是谁都应该活成自己想要的样子，一辈子只有一次，为什么不好好活一次 。

参考71. 简化路径。

题目

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

• 始终以斜杠 '/' 开头。

• 两个目录名之间必须只有一个斜杠 '/' 。

• 最后一个目录名（如果存在）不能 以 '/' 结尾。

• 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径 。

输入：path = "/a/./b/../../c/"
输出："/c"

解题思路

• 枚举：直接枚举遍历字符串,记录上次字符辅助判断。
• 栈：先使用系统api分割path,然后使用栈存储目录和..。

枚举 2ms

class Solution {
    public String simplifyPath(String path) {
        StringBuilder sb = new StringBuilder();
        char[] pc = path.toCharArray();
        int depth = 0;//记录深度 方便处理..
        char last = 0;//记录上次char 方便处理目录和/
        for(char c : pc) {
            if(c == '/') {
                if(last == '/') continue;
                else if(last == '.'){
                    //判断.前面是/还是.
                    if(sb.charAt(sb.length()-2) == '/') {//直接删除last
                        sb.deleteCharAt(sb.length()-1);
                        last = '/';
                    } else {//前面还是. 判断往上翻 还是 目录...
                        if(sb.length()>2&&sb.charAt(sb.length()-3)=='/'){//上翻
                            sb.delete(sb.length()-2,sb.length());//删 ..
                            if(depth > 0){
                                depth--;
                                sb.deleteCharAt(sb.length()-1);//删/
                                sb.delete(sb.lastIndexOf("/")+1,sb.length());//删目录
                            }
                        }else { //目录
                            sb.append(c);
                            depth++;
                        }
                        last = '/';
                    }
                } else {
                    sb.append(c);
                    last = c;
                }
            }else if(c == '.') {
                sb.append(c);
                last = '.';
            }else { //目录
                sb.append(c);
                if(last == '/') depth++;
                last = c;
            }
        }
        //后处理
        if(sb.length() > 1) {
            char end = sb.charAt(sb.length()-1);
            last = sb.charAt(sb.length()-2);
            if(end == '/') sb.deleteCharAt(sb.length()-1);
            else if(end == '.'){
                if(last == '/'){//只有一个.
                    sb.deleteCharAt(sb.length()-1);
                    if(sb.length() > 1) sb.deleteCharAt(sb.length()-1);
                } else if(last == '.') {//判断两个'.'还是三个以上
                    if(sb.length() > 2 && sb.charAt(sb.length()-3) == '/') {
                        sb.delete(sb.length()-2,sb.length());//删 ..
                        if(depth > 0){
                            sb.deleteCharAt(sb.length()-1);//删/
                            sb.delete(sb.lastIndexOf("/")+1,sb.length());//删目录
                        }
                        if(sb.length()>1) sb.deleteCharAt(sb.length()-1);//删/
                    }
                }
            }
        }
        return sb.toString();
    }
}

复杂度分析

• 时间复杂度：O(n)，一重循环遍历,n为路径长度。
• 空间复杂度：O(1)，返回结果可不计复杂度。

栈 3ms

class Solution {
    public String simplifyPath(String path) {
        String[] names = path.split("/");//只需要处理..和目录, .和空格不影响直接忽略
        Deque<String> stack = new ArrayDeque<String>();
        for (String name : names) {
            if ("..".equals(name)) {
                if (!stack.isEmpty()) {
                    stack.pollLast();
                }
            } else if (name.length() > 0 && !".".equals(name)) {
                stack.offerLast(name);
            }
        }
        StringBuffer ans = new StringBuffer();
        if (stack.isEmpty()) {
            ans.append('/');
        } else {
            while (!stack.isEmpty()) {
                ans.append('/');
                ans.append(stack.pollFirst());//poll
            }
        }
        return ans.toString();
    }
}

复杂度分析

• 时间复杂度：O(n)，n为路径长度,遍历路径和栈皆为O(n)。
• 空间复杂度：O(n)，names使用空间为n,栈使用空间不超过n,综合为O(n)。