leetcode/src/Simplify_Path.cpp at master · zyx4843/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
// Source : https://oj.leetcode.com/problems/simplify-path/
// Author : zheng yi xiong
// Date   : 2015-01-28

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

* For example,
* path = "/home/", => "/home"
* path = "/a/./b/../../c/", => "/c"

* click to show corner cases.

* 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".
*
**********************************************************************************/
#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
	string simplifyPath(string path) {
		if (path.empty())
		{
			return "/";
		}

		path.push_back('/');
		int len = path.length();
		vector<char> vec_path(len);
		vec_path[0] = '/';
		int vec_pos = 1, temp_pos = 1;
		int i = 0, j = 0;
		for (; i < len; ++i)
		{
			if ('/' == path[i])
			{
				if (vec_pos != temp_pos)
				{
					if ( (temp_pos - 1 == vec_pos) && ('.' == vec_path[temp_pos - 1]) )
					{
						//do nothing
					}
					else if ( (temp_pos - 2 == vec_pos) && ('.' == vec_path[temp_pos - 1]) && ('.' == vec_path[temp_pos - 2]) )
					{
						for (j = vec_pos - 2; j > 0; --j)
						{
							if ('/' == vec_path[j])
							{
								vec_pos = j + 1;
								vec_path[vec_pos] = 0;
								break;
							}
						}

						if (0 >= j)
						{
							vec_pos = 1;
							vec_path[1] = 0;
						}
					}
					else
					{
						vec_path[temp_pos++] = path[i];
						vec_pos = temp_pos;
					}
					temp_pos = vec_pos;
				}
			}
			else
			{
				vec_path[temp_pos++] = path[i];
			}
		}

		if ((1 != vec_pos) && ('/' == vec_path[vec_pos - 1]))
		{
			vec_path[vec_pos - 1] = 0;
		}
		else
		{
			vec_path[vec_pos] = 0;
		}

		return &vec_path[0];
	}
};

int _tmain(int argc, _TCHAR* argv[])
{
	Solution so;
	string path = "/home/foo/.ssh/../.ssh2/authorized_keys";
	string realpath = so.simplifyPath(path);
	return 0;
}