[LeetCode] 71. Simplify Path

这道题的要求是：简化（Unix/Linux风格的）文件系统路径。

会用到大概以下一些规则：

• . 代表当前目录；
• .. 代表上一级目录；

注意：它们单独使用才具有特殊意义，比如 /..abc/ 中的 “..”就没有特殊意义，不应该被简化掉。

比如：

• 路径 /home/ 简化成 /home；
• 路径 /../ 简化成 /；
• 路径 /home//foo/ 简化成 /home/foo；
• 路径 /a/./b/../../c/ 简化成 /c；
• 路径 /... 简化成 /...；
• 路径 /.hidden 简化成 /.hidden；
• 路径 /. 简化成 /.；
• ...

这道题被打上了“栈”和“字符串”的标签，于是考虑会用到栈来处理：遇到 “/./”就简化成“/”，遇到“/foo/bar/../”之类的就需要简化成“/foo/”。

也就是一个栈的应用，也不复杂，利用C++的 std::vector 实现栈的版本如下：

class Solution {
public:
	string simplifyPath(string path) {
		vector<char> v;
		const char* p = path.c_str();

		char c;
		while((c = *p++)) {
			if(c == '.' && v.size() && v.back() == '/') {
				c = *p++;
				if(c == '/') {
					continue;
				} else if(c == '.') {
					c = *p++;
					if(c == '/' || !c) {
						while(v.size() && v.back() != '/') {
							v.pop_back();
						}

						if(v.size()) v.pop_back();

						while(v.size() && v.back() != '/')
							v.pop_back();

						if(!c) break;
						else {
							if(v.size() == 0) v.push_back('/');
							continue;
						}
					}

					v.push_back('.');
					v.push_back('.');
					v.push_back(c);
					continue;
				} else if(c == 0) {
					break;
				} else {
					v.push_back('.');
					v.push_back(c);
					continue;
				}
			} else if(c == '/') {
				while(v.size() && v.back() == '/') {
					v.pop_back();
				}

				v.push_back(c);
				continue;
			} else {
				v.push_back(c);
			}
		}

		if(v.size() == 0) v.push_back('/');
		if(v.size() > 1 && v.back() == '/') v.pop_back();

		v.push_back('\0');

		return string(&v[0]);
	}
};

看起来略显复杂，其实也就那样吧～ 只要是用 std::vector 模拟了栈。

但我马上就发现了这个栈其实可以完全用指针的移动来实现，于是马上换用了C语言重写：

char* simplify_path(const char* path) {
	char* new_path = (char*)malloc(strlen(path) + 1);
	char* i = new_path;
	const char* p = path;

	char c;
	while(c = *p++) {
		if(c == '/') {
			while(i > new_path && i[-1] == '/')
				i--;

			*i++ = '/';
			continue;
		} else if(c == '.' && i[-1] == '/') {
			c = *p++;
			if(c == '/') {
				continue;
			} else if(c == '.') {
				c = *p++;
				if(c == '/' || c == '\0') {
					if(i - new_path > 1) i--;
					while(i > new_path && i[-1] != '/')
						i--;

					if(c == '\0') break;
					else continue;
				} else {
					*i++ = '.';
					*i++ = '.';
					*i++ = c;
					continue;
				}
			} else if(c == '\0') {
				break;
			} else {
				*i++ = '.';
				*i++ = c;
				continue;
			}
		} else {
			*i++ = c;
		}
	}

	if(i == new_path) *i++ = '/';
	if(i - new_path > 1 && i[-1] == '/') i--;

	*i++ = '\0';

	return (char*)new_path;
}

用C语言写的好处非常多，可以看到：少了很多次的入栈/出栈/计算大小的函数调用(换成了指针的移动）；而且至多进行一次内存分配，实际上，如果传入的参数允许修改的话，根本无需进行内存分配，因为：简化后的路径长度只可能少于或等于原路径的长度，所以可以直接在原路径上面修改就行。（C的效率就体现在这些方方面面）

这里是一张官方截至今天的统计图，看到“You are here”了吗？ :-)

这张图说明了什么？