首页 > 代码库 > [Leetcode] Simplify path 简化路径

[Leetcode] Simplify path 简化路径

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

For example,
path ="/home/", =>"/home"
path ="/a/./b/../../c/", =>"/c"

click to show corner cases.

Corner Cases:

 

  • Did you consider the case where path ="/../"?
    In this case, you should return"/".
  • Another corner case is the path might contain multiple slashes‘/‘together, such as"/home//foo/".
    In this case, you should ignore redundant slashes and return"/home/foo".
 题意:简化路径,这题的解决方法是弄懂题意。给题加上两个例子,path = "/a/./b/../c/", => "/a/c"和path = "/a/./b/c/", => "/a/b/c"。规律如下:
1)两个‘ / ‘之间为 ‘ . ‘,表示本级目录,直接去掉;
2)两个‘ / ‘之间为 ‘ .. ‘,表示返回上一级目录,即,".."时删掉它上面挨着的一个路径,但之前要检查上一级是否为空;
3)如果为空,则返回 ‘ / ‘;
4)遇到‘ // ‘,即两个连在一起,就返回一个‘ / ‘;
思路:从上面的规律可知,如何简化路径主要在于两个 ‘ / ‘之间的字符是什么,所以,采取的方法是:将路径看做是由一个或多个"/"分割开的多个子字符串,分别对其处理即可。
采用stack,每找到一个dir, 如果不是"."或者"..",就压入stack,如果是"..",就从stack弹出一个,最后把stack里的dir组合成一个string。但stack结构不方便组成一个string,所以这里使用向量,代码如下:
 1 class Solution {
 2 public:
 3     string simplifyPath(string path) 
 4     {
 5         vector<string> res;
 6 
 7         for(int i=0;i<path.size();)
 8         {
 9             i++;
10             if(i==path.size())    break;  //注意i++后会越界
11             int flag=i;
12             while(path[i] !=/&&i<path.size())   //注意i++后会越界
13                 i++;
14             
15             string dir=path.substr(flag,i-flag);  //substr()的参数为起点和个数
16 
17             if( !dir.empty()&&dir !=".")
18             {
19                 if(dir=="..")
20                 {
21                     if( !res.empty())
22                         res.pop_back();
23                 }
24                 else
25                     res.push_back(dir);
26             }
27             
28         } 
29 
30         if(res.empty())
31             return "/";
32 
33         string result;
34         for(int i=0;i<res.size();++i)
35         {
36             result+=/+res[i];
37         }   
38         
39         return result; 
40     }
41 };

 还有一种同样的思路但是采用迭代器的,见连接1。

[Leetcode] Simplify path 简化路径