LeetCode 71. Simplify Path（路径简化）

发布时间：2022-10-10 11:16:31 所属栏目：Unix 来源：

导读：　　题目描述：

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

　　For example,

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

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

　　Corner Cases:

　　题目描述：

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

　　For example,

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

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

　　Corner Cases:

　　分析：

　　题意：给定一个Unix风格的字符串路径，返回他的简化结果。

　　思路：这道题考察栈stack的使用。根据题目的规则，遇到"/../"省略上一级的目录，"/./"略过不做处理，"//"等价于"/"。由于路径是一个多层级结构，可以采用stack解决，我们从左到右扫描字符串，以为"/"分割界限：① 遇到".."的，如果stack不为空，则弹出栈顶元素（相当于省略上一级的目录）；② 遇到"."和""的，直接略过不处理；③ 遇到其他字符子串，把它加入到stack中；④ 扫描完之后，把stack中的元素逐个弹出，按逆序加入到答案中unix路径简化，用"/"连接。

　　假设源路径字符串长度为n，时间复杂度为O(n)。

　　代码：

　　#include
　　using namespace std;
　　class Solution {
　　public:
　　    string simplifyPath(string path) {
　　        int n = path.length();
　　 // Exceptional Case:
　　 if(n == 0){
　　 return path;
　　 }
　　 path += "/";
　　 string ans = "", str;
　　 stack st;
　　 int start = 0, end = 1;
　　 while(end <= n){
　　 if(path[end] != '/'){
　　 end++;
　　 }
　　 else{
　　 if(end - start - 1 >= 1){
　　 str = path.substr(start + 1, end - start - 1);
　　 if(str == ".."){
　　 if(!st.empty()){
　　 st.pop();
　　 }
　　 }
　　 else if(str != "." && str != ""){
　　 st.push(str);
　　 }
　　 }
　　 start = end;
　　 end = start + 1;
　　 }
　　 }
　　 while(!st.empty()){
　　 str = st.top();
　　 st.pop();
　　 ans.insert(0, "/" + str);
　　 }
　　 if(ans == ""){
　　 ans = "/";
　　 }
　　 return ans;
　　    }
　　};

（编辑：开发网_新乡站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!