Simplify Path

LeetCode
, , ,

第三天（hhh，好像又很久没刷了）, 又AC掉了逻辑题，或者说又是一道用if else加状态机搞定的题。

今天的题目是71. Simplify Path

以后还是不copy题目到这里来了，有点麻烦的感觉。。。

对于这种纯看逻辑的题目，可以先分析一下给出的测例，然后通过题目来分析要注意什么：

  1. “/home/“
  2. “/../“
  3. “/home//foo/“
  4. “/a/./b/../../c/“
  5. “/a/../../b/../c//.//“
  6. “/a//b////c/d//././/..”

从上面我们大概可以知道要注意的一些点有：

  • 首先疑似最开始的符号一定是’/‘？
  • 通过/来分割单词，这意味着我们可以用python中的split或者先做一次遍历来分割单词，这样做会简化逻辑（但我没用这种方法）
  • 要区分.和..
  • .表示当前目录，..表示上级目录
  • 遇到多个/，就当成一个

事实上在后面的测试中，我发现一个很坑的点，就是...和..a这种并不是一个特殊的字符串，可以作为路径名。

我们现在尝试写一个基于状态机的方法，首先定义一下遍历时需要的状态：

  1. 前面是一个正常的字符
    • 遇到/,就插入到结果字符串中，并跳转到1。
    • 遇到.，就跳转到2。
    • 遇到一个正常的字符，插入到结果字符串中。
  2. 前面是/
    • 如果遇到一个/，就直接跳过
    • 如果遇到一个.,跳转到2
    • 如果是一个正常字符，就插入到结果字符串中并跳转到0
  3. 前面是.
    • 如果遇到一个/, 就跳转到1
    • 如果遇到一个.,就跳转到3
    • 如果遇到一个正常字符，就插入.和这个字符，并跳转到0
  4. 前面是..
    • 如果遇到一个/,就开始回溯删除到前面一个/
    • 其余则插入一个..和这个字符，并跳转到0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
    string simplifyPath(string path) {
        string res;
        
        // some flag to kepp state.
        int state = 0;  // 0: last char is [char]
                        // 1: last char is '/'
                        // 2: last char is '.'
                        // 3: last char is ".."
        
        if (path.size() != 0 && path[path.size()-1]!='/') path.push_back('/');
        
        int len = path.size();
        for(int i = 0; i < len; i++) {
            char c = path[i];
            
            if (state == 0) {
                if (c == '/') { res.push_back('/'); state = 1; }
                else if (c == '.') state = 2;
                else res.push_back(c);
            } else if (state == 1) {
                if (c == '/') {}
                else if (c == '.') { state = 2; }
                else {
                    res.push_back(c); state = 0;
                }
            } else if (state == 2) {
                if (c == '/') state = 1;
                else if (c == '.') {
                    // '..'
                    state = 3;
                } else {
                    res.push_back('.'); res.push_back(c); state = 0;
                }
            } else if (state == 3) {
                if (c == '/') {
                    // go back
                    res.pop_back(); // pop '/'
                    while(res.size() != 0 && *res.rbegin() != '/') {
                        res.pop_back(); // pop anthing until '/'
                    }
                    if (res.size() == 0) res.push_back('/');
                    state = 1;
                } else {
                    res.push_back('.'); 
                    res.push_back('.');
                    res.push_back(c);
                    state = 0;
                }
            }
            //cout << state << " " << c << " " << res <<  endl;
        }
        
        if ((state == 1 && res.size() != 1)) res.pop_back();
        return res;
    }
};

update at 2020-03-23

状态转移图：

FSM

这道题其实用栈会更简单一点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
string simplifyPath(string path) {
    
    vector<string> st;
    int beg = 0;
    path.push_back('/');
    for(int i = 0, sz = path.size(); i < sz; i++) {
        if (path[i] == '/') {
            auto s = path.substr(beg, i-beg);
            beg = i + 1;
            if (s == "." || s.size() == 0) {
                // do nothing
            } else if (s == "..") {
                if (st.size() != 0) st.pop_back(); // make sure '/../' is ok
            } else st.push_back(s);
        }
    }
    string res;
    for(auto &s: st) {
        // cout << s << endl;
        res.push_back('/');
        res += s;
    }
    if (res.size() == 0) res.push_back('/'); 
    return res;
}

用stringstream和getline来进行字符串分割：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string simplifyPath(string path) {
    string buf;
    istringstream ss(path);
    vector<string> st;
    while(getline(ss, buf, '/')) {
        // cout << buf << endl;
        if (buf == "." || buf.size() == 0) {

        } else if (buf == ".."){
            if (st.size() != 0) st.pop_back();
        }
        else st.push_back(buf);
    }
    string res;
    for (auto &s: st) {
        res.push_back('/');
        res += s;
    }
    if (res.size() == 0) res.push_back('/');
    return res;
}