forked from liuyubobobo/Play-Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.cpp
77 lines (57 loc) · 1.85 KB
/
main.cpp
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
/// Source : https://leetcode.com/problems/find-duplicate-file-in-system/
/// Author : liuyubobobo
/// Time : 2021-05-18
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
/// Using HashMap
/// Time Complexity: O(|all files|)
/// Space Complexity: O(|all files|)
class Solution {
public:
vector<vector<string>> findDuplicate(vector<string>& paths) {
unordered_map<string, vector<string>> table;
for(const string& path: paths){
vector<string> v = split(path);
for(int i = 1; i < v.size(); i ++){
vector<string> file = parse(v[i]);
table[file[1]].push_back(v[0] + "/" + file[0]);
}
}
vector<vector<string>> res;
for(const pair<string, vector<string>>& p: table)
if(p.second.size() > 1)
res.push_back(p.second);
return res;
}
private:
vector<string> parse(const string& s){
int l = s.find('(');
assert(l != string::npos);
int r = s.find(')', l + 1);
assert(r != string::npos);
return {s.substr(0, l), s.substr(l + 1, r - l - 1)};
}
vector<string> split(const string& s){
vector<string> res;
for(int start = 0, i = 1; i <= s.size(); i ++)
if(i == s.size() || s[i] == ' '){
res.push_back(s.substr(start, i - start));
start = i + 1;
i = start;
}
return res;
}
};
void print(const vector<vector<string>>& res){
for(const vector<string>& v: res){
for(const string& s: v) cout << s << " "; cout << endl;
}
}
int main() {
vector<string> paths1 = {"root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"};
print(Solution().findDuplicate(paths1));
return 0;
}