一、 题目描述
二、解题思路
使用哈希表来实现。首先提取字符串中的内容，形成k e y = C o n t e n t , v a l u e = P a t h key = Content, value = Pathkey=Content,value=Path的p a i r pairpair。之后建立一个k e y keykey为s t r i n g stringstring类、v a l u e valuevalue为v e c t o r < v e c t o r < s t r i n g > > vector<vector<string>>vector<vector<string>>类型的u n o r d e r e d unorderedunordered_ m a p mapmap。之所以采用u n o r d e r e d unorderedunordered_m a p mapmap是因为其内部实现为哈希表。遍历一遍v e c t o r < s t r i n g > p a t h s vector<string> pathsvector<string>paths，在创造p a i r pairpair的过程中查看在u n o r d e r e d unorderedunordered _m a p mapmap里是否存在与k e y = C o n t e n t key = Contentkey=Content相等的p a i r pairpair，如果有，就把当前这个p a i r pairpair的v a l u e = s t r i n g value = stringvalue=string插入到这个值对应的v e c t o r < s t r i n g > vector<string>vector<string>里。
三、解题代码
class Solution {
private:
pair<string, string> CreateDocPair(string str, string rootPath){
int prior = 0;
for(; prior < str.size() && str[prior] != '('; prior++);
auto Name = rootPath + "/" + str.substr(0, prior);
auto Content = str.substr(prior + 1, str.size() - 1 - (prior + 1));
return make_pair(Content, Name);
}
public:
vector<vector<string>> findDuplicate(vector<string>& paths) {
unordered_map<string, vector<string>> mp;
vector<pair<string, string>> doc;
for(int i = 0; i < paths.size(); i++)
{
auto tmpCMD = paths[i];
int prior = 0;
for(; prior < tmpCMD.size() && tmpCMD[prior] != ' '; prior++);
auto rootPath = tmpCMD.substr(0, prior++);
for(; prior < tmpCMD.size(); prior++){
int ahead = prior;
for(; ahead < tmpCMD.size() && tmpCMD[ahead] != ' '; ahead++);
auto ret = CreateDocPair(tmpCMD.substr(prior, ahead - prior), rootPath);
prior = ahead;
mp[ret.first].push_back(ret.second);
}
}
vector<vector<string>> sln;
for(auto it: mp)
if(it.second.size() > 1) sln.push_back(it.second);
return sln;
}
};
四、运行结果
