一、 题目描述
二、解题思路
使用哈希表来实现。首先提取字符串中的内容，形成 k e y = C o n t e n t , v a l u e = P a t h key = Content, value = Path key=Content,value=Path的 p a i r pair pair。之后建立一个 k e y key key为 s t r i n g string string类、 v a l u e value value为 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 unordered unordered_ m a p map map。之所以采用 u n o r d e r e d unordered unordered_ m a p map map是因为其内部实现为哈希表。遍历一遍 v e c t o r < s t r i n g > p a t h s vector<string> paths vector<string>paths，在创造 p a i r pair pair的过程中查看在 u n o r d e r e d unordered unordered _ m a p map map里是否存在与 k e y = C o n t e n t key = Content key=Content相等的 p a i r pair pair，如果有，就把当前这个 p a i r pair pair的 v a l u e = s t r i n g value = string value=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;
}
};
京公网安备 11010502036488号