Code & Func

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

今天的题目是71. Simplify Path

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

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

“/home/”
”/../”
“/home//foo/”
“/a/./b/../../c/”
“/a/../../b/../c//.//”
“/a//b////c/d//././/..”

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

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

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

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

前面是一个正常的字符
- 遇到/,就插入到结果字符串中，并跳转到1。
- 遇到.，就跳转到2。
- 遇到一个正常的字符，插入到结果字符串中。
前面是/
- 如果遇到一个/，就直接跳过
- 如果遇到一个.,跳转到2
- 如果是一个正常字符，就插入到结果字符串中并跳转到0
前面是.
- 如果遇到一个/, 就跳转到1
- 如果遇到一个.,就跳转到3
- 如果遇到一个正常字符，就插入.和这个字符，并跳转到0
前面是..
- 如果遇到一个/,就开始回溯删除到前面一个/
- 其余则插入一个..和这个字符，并跳转到0

1
class Solution {
2
public:
3
    string simplifyPath(string path) {
4
        string res;
5

6
        // some flag to kepp state.
7
        int state = 0;  // 0: last char is [char]
8
                        // 1: last char is '/'
9
                        // 2: last char is '.'
10
                        // 3: last char is ".."
11

12
        if (path.size() != 0 && path[path.size()-1]!='/') path.push_back('/');
13

14
        int len = path.size();
15
        for(int i = 0; i < len; i++) {
43 collapsed lines
16
            char c = path[i];
17

18
            if (state == 0) {
19
                if (c == '/') { res.push_back('/'); state = 1; }
20
                else if (c == '.') state = 2;
21
                else res.push_back(c);
22
            } else if (state == 1) {
23
                if (c == '/') {}
24
                else if (c == '.') { state = 2; }
25
                else {
26
                    res.push_back(c); state = 0;
27
                }
28
            } else if (state == 2) {
29
                if (c == '/') state = 1;
30
                else if (c == '.') {
31
                    // '..'
32
                    state = 3;
33
                } else {
34
                    res.push_back('.'); res.push_back(c); state = 0;
35
                }
36
            } else if (state == 3) {
37
                if (c == '/') {
38
                    // go back
39
                    res.pop_back(); // pop '/'
40
                    while(res.size() != 0 && *res.rbegin() != '/') {
41
                        res.pop_back(); // pop anthing until '/'
42
                    }
43
                    if (res.size() == 0) res.push_back('/');
44
                    state = 1;
45
                } else {
46
                    res.push_back('.');
47
                    res.push_back('.');
48
                    res.push_back(c);
49
                    state = 0;
50
                }
51
            }
52
            //cout << state << " " << c << " " << res <<  endl;
53
        }
54

55
        if ((state == 1 && res.size() != 1)) res.pop_back();
56
        return res;
57
    }
58
};

update at 2020-03-23

状态转移图：

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

1
string simplifyPath(string path) {
2

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

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

1
string simplifyPath(string path) {
2
    string buf;
3
    istringstream ss(path);
4
    vector<string> st;
5
    while(getline(ss, buf, '/')) {
6
        // cout << buf << endl;
7
        if (buf == "." || buf.size() == 0) {
8

9
        } else if (buf == ".."){
10
            if (st.size() != 0) st.pop_back();
11
        }
12
        else st.push_back(buf);
13
    }
14
    string res;
15
    for (auto &s: st) {
6 collapsed lines
16
        res.push_back('/');
17
        res += s;
18
    }
19
    if (res.size() == 0) res.push_back('/');
20
    return res;
21
}