LeetCode71：简化路径

红太狼 2021-05-10 11:33 466阅读 0赞

## 71. 简化路径 ##

### 1. 问题重述 ###

将Unix风格的文件路径简化及合法化 , 防止用户恶意输入路径

> 请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。

> 示例 1：
> 
>  *  输入："/home/"
>  *  输出："/home"
>  *  解释：注意，最后一个目录名后面没有斜杠。
> 
> 示例 2：
> 
>  *  输入："/…/"
>  *  输出："/"
>  *  解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
> 
> 示例 3：
> 
>  *  输入："/home//foo/"
>  *  输出："/home/foo"
>  *  解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
> 
> 示例 4：
> 
>  *  输入："/a/./b/…/…/c/"
>  *  输出："/c"
> 
> 示例 5：
> 
>  *  输入："/a/…/…/b/…/c//.//"
>  *  输出："/c"
> 
> 示例 6：
> 
>  *  输入："/a//bc/d//././/…"
>  *  输出："/a/b/c"

### 2. 解题思路 ###

> 1.  在确定不会它输入变态的/a/a/a/a/a/a/a后 , 我可以放心地大胆想思路了
> 2.  既然最后要以 "/"开头 , 我无法保证它一开始输入的路径就是正确的 , 而且恰好在Unix下目录之间以 “/” 来分隔 , 那么我先把所有的目录分隔符都去掉 , 在得出正确的结果后再自己在每个目录之间添加 “/” 就好了
> 3.  利用栈来保存每一个目录 , 要考虑两种特殊情况
>     
>      *  " . . "
>     
>     遇到返回上一级目录标识符时 :
>     
>     1.  需要**对栈进行判空** , 因为示例2表明无法从根目录返回上一级目录 , 如果栈为空 , 那么此标识符就没必要操作了
>     2.  如果栈不为空 , 那么遇到此标识符就弹出栈顶的那一个目录 , 因为进入目录a再返回上一级目录 , 就等于没有进入目录a
>         
>         示例 : **" /a/…/ " = " / "**
>     
>      *  " . "
>         
>         遇到表示当前目录本身的标识符时 , 直接跳过 , 因为它不对我们的目录路径造成任何影响

### 3. 注意事项 ###

1.  我们对路径以斜杠(/)进行切割时 , **返回上一级目录标识符(…)是一个字符串 , 当前目录本身标识符( . )又是另外一个字符串** , 所以切割后并不会出现( … )这种情况
2.  如果存在**多个目录分隔符连续**的情况 , 分割后会出现有空串的情况出现("") , 此时也要进行过滤

### 4. 编码实现 ###

class Solution { 
        public String simplifyPath(String path) { 
            Stack<String> stack = new Stack<String>();
            //以"/"切割字符串
            String[] split = path.split("/");
            for (int i = 0; i < split.length; i++) { 
                switch (split[i]){ 
                    case "..":
                        //栈判空, 如果为空则没有意义
                        if(stack.isEmpty()){ 
                            break;
                        }else{ 
                            //合法,则弹出栈顶的"."和栈顶的后一个元素,因为抵消了
                            stack.pop();
                        }
                        break;
                    //遇到""不进行任何操作
                    case "":
                        break;
                    //遇到"."不进行任何操作
                    case ".":
                        break;
                    default:
                        stack.push(split[i]);
                        break;
                }
            }
            //如果栈为空则说明是根目录
            if(stack.isEmpty()){ 
                return "/";
            }else{ 
                //将栈里的元素一个一个取出来,并为其中间和最前面添加上"/"
                StringBuilder str = new StringBuilder();
                for (int i = 0; i < stack.size(); i++) { 
                    str.append("/"+stack.get(i));
                }
                return str.toString();
            }
        }
    }

### 5. 成绩 ###

![成绩][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70]: /images/20210509/5a04bdd5639d4c4d82e48e867ddd6cb5.png