Simplify Path

描述

Given an absolute path for a file (Unix-style), simplify it.

For example,

  • path = "/home/", => "/home"

  • path = "/a/./b/../../c/", => "/c"
    Corner Cases:

  • Did you consider the case where path = "/../"?

    In this case, you should return "/".

  • Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".

    In this case, you should ignore redundant slashes and return "/home/foo".

分析

很有实际价值的题目。

代码

  1. // Simplify Path
  2. // 时间复杂度O(n)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     string simplifyPath(const string& path) {
  6.         vector<string> dirs; // 当做栈
  8.         for (auto i = path.begin(); i != path.end();) {
  9.             ++i;
  11.             auto j = find(i, path.end(), '/');
  12.             auto dir = string(i, j);
  14.             if (!dir.empty() && dir != ".") {// 当有连续 '///'时，dir 为空
  15.                 if (dir == "..") {
  16.                     if (!dirs.empty())
  17.                         dirs.pop_back();
  18.                 } else
  19.                     dirs.push_back(dir);
  20.             }
  22.             i = j;
  23.         }
  25.         stringstream out;
  26.         if (dirs.empty()) {
  27.             out << "/";
  28.         } else {
  29.             for (auto dir : dirs)
  30.                 out << '/' << dir;
  31.         }
  33.         return out.str();
  34.     }
  35. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/string/simplify-path.html