leet_code/71.simpifyPath.cc at master · pagict/leet_code · 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
105
106
107
108
109
110
111
112
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
#include <iostream>

/// 3ms
/// Beats 91.41%of users with C++
/// 7.43MB
/// Beats 98.25%of users with C++
std::string simplifyPath(std::string path) {
  std::vector<std::pair<int, size_t>> components;

  int i = 0;
  int first = 0;
  while (i < path.size()) {
    char c = path[i];
    if (c == '/') {
      if (first <=i - 1) {
        components.push_back({first, i - first});
      }
      ++i;
      first = i;
      continue;
    }

    if (c == '.') {
      if (first < i) {
        ++i;
      } else {
        if (i+1 == path.size() || path[i+1] == '/') {
          i = i + 2;
          first = i;
          continue;
        }

        if (path[i+1] == '.') {
          if (i+2 == path.size() || path[i+2] == '/') {
            if (!components.empty()) {
              components.pop_back();
            }
            i = i + 3;
            first = i;
            continue;
          }

          i = i + 3;
        } else {
          i = i + 2;
        }
      }
    } else {
      ++i;
    }
  }
  if (i > first) {
    components.push_back({first, i - first});
  }

  int total_len = 0;
  for (const auto &c : components) {
    total_len += c.second;
  }
  total_len += components.size();
  if (!total_len) {
    total_len = 1;
  }
  std::string ret(total_len, '/');
  int offset = 1;
  for (const auto& c : components) {
    for (auto i = 0; i < c.second; ++i) {
      ret[offset + i] = path[c.first + i];
    }
    offset += c.second;
    ++offset;
  }
  return ret;
}

int main(int argc, char** argv) {
  std::vector<std::pair<std::string, std::string>> cases{
    {"/axb/sxd/sx", "/axb/sxd/sx"},
    {"/axx/.", "/axx"},
    {"/ax/./ssx", "/ax/ssx"},
    {"/a.x/x", "/a.x/x"},
    {"/asx/.s", "/asx/.s"},
    {"/xd/../sx/.", "/sx"},
    {"/sxx/.sd/../a", "/sxx/a"},
    {"/", ""},
    {"/.", "/"},
    {"/..", "/"},
    {"/sx/", "/sx"},
    {"/../", "/"},
    {"/a/./b/../../c/", "/c"},
    {"/home//s", "/home/s"},
    {"/home/", "/home"},
    {"/...", ""},
    {"/as..sdf", ""}
  };
  for(auto& c : cases) {
    auto tmp = simplifyPath(c.first);
    auto expect = c.second;
    if (expect.empty()) expect = c.first;
    if (tmp != expect) {
      std::cout << "!!! " << c.first << " -> " << tmp << std::endl;
    }
    else {
       std::cout << c.first << " -> " << tmp << std::endl;
    }
  }
  return 0;
}