71. Simplify Path.md

71. Simplify Path

思路

题目要求简化unix的路径字符串。由题意知:

• . 代表当前目录，所以可忽略；
• .. 代表上一个目录，所以应该进入上一个目录（即pop掉当前目录）；
• 连续多个/只代表一个/。

因此我们可以根据以上规则，遍历一遍path字符串，用一个栈stk记录进入的文件夹名称，遍历完成后stk中即记录了简化后的路径名。
根据如何通过path得到每个文件名，可分为两个思路: 双指针法和getline法。

思路一: 双指针法

定义两个指针low和high, low代表当前文件夹名称的第一个字符的前一个位置(所以肯定指向/), high代表当前文件夹名称的最后一个字符的位置。然后判断low和high之间组成的字符是否是/.或/..即可。例如:

path: //dir1/../
index:0123456789...

则第一次循环时, low = 1, high = 5, 其间组成的文件夹字符串为/dir1，不是/.或/..，应该将/dir1其push进stk； 第二次循环时，文件夹字符串为/..，应该将stk中的/dir1其pop出来；......
时空复杂度均为O(n)

思路二: getline法

利用头文件string下的getline函数可以很方便的以/为分隔符将path分开，然后就和思路一类似了。
C++中的getline用法可参考此处:

在C++中本质上有两种getline函数, 一种在头文件istream中，是istream类的成员函数, 另一种在头文件string中，是普通函数。这里我们用到的是第二种。

在头文件string中的getline函数有四种重载形式：

istream& getline (istream&  is, string& str, char delim);
istream& getline (istream&& is, string& str, char delim);
istream& getline (istream&  is, string& str);
istream& getline (istream&& is, string& str);

函数的变量：

is    ：表示一个输入流，例如cin。本题我们用到的是stringstream或者istringstream。
str   ：string类型的引用，用来存储输入流中的流信息。
delim ：char类型的变量，所设置的截断字符；在不自定义设置的情况下，遇到’\n’，则终止输入。

时空复杂度也都为O(n)
注: 关于C++中的stringstream等输入输出流的用法可见此处。

C++

思路一

class Solution {
public:
    string simplifyPath(string path) {
        vector<string>stk;        
        int low = 0, high, len = path.size();
        string res = "";
        
        while(low < len){ // 每次循环得到一个文件夹的名称(以"/"开头, 例如"/.","/..","/a")
            while(low < len - 1 && path[low + 1] == '/') low++; 
            high = low + 1;
            while(high < len - 1 && path[high + 1] != '/') high++; 
            if(high == len) break;
            string dir = "";
            for(int i = low; i <= high; i++) dir += path[i]; // dir表示当前文件夹，以"/"开头
            if(dir == "/.."){
                if(!stk.empty()) stk.pop_back();
            }
            else if(dir != "/.") stk.push_back(dir);
            
            low = high + 1;
        }
        for(string dir: stk) res += dir;
        return stk.empty()? "/" : res;
    }
};

思路二

class Solution {
public:
    string simplifyPath(string path) {
        string res, tmp;
        vector<string> stk;
        stringstream ss(path); // or istringstream ss(path);
        while(getline(ss,tmp,'/')) {
            if (tmp == "" or tmp == ".") continue;
            if (tmp == ".." and !stk.empty()) stk.pop_back();
            else if (tmp != "..") stk.push_back(tmp);
        }
        for(string str : stk) res += "/"+str;
        return res.empty() ? "/" : res;
    }
};