LintCode 421 Simplify Path (字符串处理题)

本文主要是介绍LintCode 421 Simplify Path (字符串处理题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

421 · Simplify Path
Algorithms

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

In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period … moves the directory up a level.

The result must always begin with /, and there must be only a single / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the result must be the shortest string representing the absolute path.

Did you consider the case where path is “/…/”?

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”.

Example
Example 1:

Input: “/home/”
Output: “/home”
Example 2:

Input: “/a/./…/…/c/”
Output: “/c”
Explanation: “/” has no parent directory, so “/…/” equals “/”.
Tags
Company
OpenAI
Facebook
Microsoft

class Solution {
public:/*** @param path: the original path* @return: the simplified path*/string simplifyPath(string &path) {int n = path.size();string res = "";int pos = 0, dirStartPos = 0, dirEndPos = 0;stack<string> stk;while (pos < n) {while (pos < n && path[pos] == '/') pos++;dirStartPos = pos;while (pos < n && path[pos] != '/') pos++;dirEndPos = pos;string dirStr = path.substr(dirStartPos, dirEndPos - dirStartPos);if (dirStr == "..") {if (!stk.empty()) stk.pop();} else if (dirStr.size() > 0 && dirStr != ".") {stk.push(dirStr);}}while (!stk.empty()) {res = "/" + stk.top() + res;stk.pop(); }if (res.size() == 0) res = "/";return res;}
};

不用stack用vector也可以。

class Solution {
public:/*** @param path: the original path* @return: the simplified path*/string simplifyPath(string &path) {vector<string> dirs;int pos = 0;while (pos < path.size()) {while (path[pos] == '/' && pos < path.size()) ++pos;if (pos == path.size()) break;int startPos = pos;while (path[pos] != '/' && pos < path.size()) ++pos;int endPos = pos - 1;string s = path.substr(startPos, endPos - startPos + 1);if (s == "..") {if (!dirs.empty()) dirs.pop_back();} else if (s != ".") {dirs.push_back(s);}}if (dirs.empty()) return "/";string result;for (int i = 0; i < dirs.size(); ++i) {result += '/' + dirs[i];}return result;}
};