当前位置：首页 > article >正文

Leetcode 71 Simply Path

article 2024/10/18 9:53:13

题意：给定一个字符串我要得到简化后的路径。 '…‘代表上个路径，’.'代表当前路径

Input: path = “/home/user/Documents/…/Pictures”

Output: “/home/user/Pictures”
https://leetcode.com/problems/simplify-path/description/

解析：首先这道题肯定是从头到尾遍历来做，难点在于我应该用什么判断语句。
如果结尾能够+一个‘/’判断会少很多。用一个cur变量来保存当前可以进入栈的元素，用一个栈来存放当前所有的路径，最后重组即可。

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> st;
        string cur;
        string ret;
        if(path.back() != '/') {
            path += '/';
        }
        for(int i = 0; i < path.size(); i++) {
            if(path[i] != '/') {
               cur += path[i];
               continue;
            } else {
                if (cur == "..") {
                    if(st.size()) {
                    st.pop_back();
                    }
                } else if (cur != "." && cur.size()) {
                    st.push_back(cur);
                }
                cur.clear();
            }

        }
            if(!st.size()) return "/";
            for(auto&p : st) {
                ret += '/';
                ret += p;
            }
            return ret;
    }
};

Leetcode 71(错误答案)

这种情形没有考虑到/…hidden/的情形

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> st;
        string ret;
        for(int i = 0; i < path.size(); i++) {
            if(isalpha(path[i])) {
                int j = i;
                while(isalpha(path[j])) j++;
                string p = path.substr(i, j-i);
                st.push_back(p);
                i = j - 1;
            }
            if(path[i] == '.')  {
                int j = i;
                while((path[j] == '.')) j++;
                // one dot
                if(j-i == 1)
                    continue;
                if(j-i == 2) {
                    if(st.size()) {
                        st.pop_back();
                    }
                }
                if(j-i > 2) {
                    string p = path.substr(i, j-i);
                    st.push_back(p);
                }
                i = j - 1;
            }
            if(path[i] == '/') continue;
        }
            if (!st.size()) {
                return "/";
            }
            for(auto&p : st) {
                ret += '/';
                ret += p;
            }
            return ret;
    }
};