71.SimplifyPath.cpp

/*
 * @lc app=leetcode id=71 lang=cpp
 *
 * [71] Simplify Path
 *
 * https://leetcode.com/problems/simplify-path/description/
 *
 * algorithms
 * Medium (34.63%)
 * Likes:    348
 * Dislikes: 101
 * Total Accepted:    275.4K
 * Total Submissions: 786.7K
 * Testcase Example:  '"/home/"'
 *
 * Given a string path, which is an absolute path (starting with a slash '/')
 * to a file or directory in a Unix-style file system, convert it to the
 * simplified canonical path.
 *
 * In a Unix-style file system, a period '.' refers to the current directory, a
 * double period '..' refers to the directory up a level, and any multiple
 * consecutive slashes (i.e. '//') are treated as a single slash '/'. For this
 * problem, any other format of periods such as '...' are treated as
 * file/directory names.
 *
 * The canonical path should have the following format:
 *
 *
 * The path starts with a single slash '/'.
 * Any two directories are separated by a single slash '/'.
 * The path does not end with a trailing '/'.
 * The path only contains the directories on the path from the root directory
 * to the target file or directory (i.e., no period '.' or double period
 * '..')
 *
 *
 * Return the simplified canonical path.
 *
 *
 * Example 1:
 *
 *
 * Input: path = "/home/"
 * Output: "/home"
 * Explanation: Note that there is no trailing slash after the last directory
 * name.
 *
 *
 * Example 2:
 *
 *
 * Input: path = "/../"
 * Output: "/"
 * Explanation: Going one level up from the root directory is a no-op, as the
 * root level is the highest level you can go.
 *
 *
 * Example 3:
 *
 *
 * Input: path = "/home//foo/"
 * Output: "/home/foo"
 * Explanation: In the canonical path, multiple consecutive slashes are
 * replaced by a single one.
 *
 *
 * Example 4:
 *
 *
 * Input: path = "/a/./b/../../c/"
 * Output: "/c"
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= path.length <= 3000
 * path consists of English letters, digits, period '.', slash '/' or '_'.
 * path is a valid absolute Unix path.
 *
 *
 */

// @lc code=start
#include <string>
#include <vector>

class Solution {
public:
    std::string simplifyPath(std::string path) {
        std::vector<std::string> folders;
        int idx = 0;
        while (idx < path.length()) {
            while (idx < path.length() && path[idx] == '/') idx++;
            std::string f = "";
            while (idx < path.length() && path[idx] != '/') {
                f += path[idx];
                idx++;
            }
            if (f == ".") {
                continue;
            } else if (f == "..") {
                if (!folders.empty()) {
                    folders.pop_back();
                }
            } else if (f.length()) {
                folders.push_back(f);
            }
        }

        std::string result = "";
        for (auto fo : folders) {
            result += "/";
            result += fo;
        }
        if (result.empty()) {
            result = "/";
        }
        return result;
    }
};
// @lc code=end