<p>Given a list <code>paths</code> of directory info, including the directory path, and all the files with contents in this directory, return <em>all the duplicate files in the file system in terms of their paths</em>. You may return the answer in <strong>any order</strong>.</p>

<p>A group of duplicate files consists of at least two files that have the same content.</p>

<p>A single directory info string in the input list has the following format:</p>

<ul>
	<li><code>&quot;root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)&quot;</code></li>
</ul>

<p>It means there are <code>n</code> files <code>(f1.txt, f2.txt ... fn.txt)</code> with content <code>(f1_content, f2_content ... fn_content)</code> respectively in the directory &quot;<code>root/d1/d2/.../dm&quot;</code>. Note that <code>n &gt;= 1</code> and <code>m &gt;= 0</code>. If <code>m = 0</code>, it means the directory is just the root directory.</p>

<p>The output is a list of groups of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format:</p>

<ul>
	<li><code>&quot;directory_path/file_name.txt&quot;</code></li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"]
<strong>Output:</strong> [["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)"]
<strong>Output:</strong> [["root/a/2.txt","root/c/d/4.txt"],["root/a/1.txt","root/c/3.txt"]]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= paths.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= paths[i].length &lt;= 3000</code></li>
	<li><code>1 &lt;= sum(paths[i].length) &lt;= 5 * 10<sup>5</sup></code></li>
	<li><code>paths[i]</code> consist of English letters, digits, <code>&#39;/&#39;</code>, <code>&#39;.&#39;</code>, <code>&#39;(&#39;</code>, <code>&#39;)&#39;</code>, and <code>&#39; &#39;</code>.</li>
	<li>You may assume no files or directories share the same name in the same directory.</li>
	<li>You may assume each given directory info represents a unique directory. A single blank space separates the directory path and file info.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong></p>

<ul>
	<li>Imagine you are given a real file system, how will you search files? DFS or BFS?</li>
	<li>If the file content is very large (GB level), how will you modify your solution?</li>
	<li>If you can only read the file by 1kb each time, how will you modify your solution?</li>
	<li>What is the time complexity of your modified solution? What is the most time-consuming part and memory-consuming part of it? How to optimize?</li>
	<li>How to make sure the duplicated files you find are not false positive?</li>
</ul>

class Solution {
public:
    void print2dvec(vector<vector<string>> filesPath){
        for (int i = 0; i < filesPath.size(); i++)
        {
            for (int j = 0; j < filesPath[i].size(); j++)
            {
                cout << filesPath[i][j] << " ";
            }
            cout << endl;
        }
    }
    vector<vector<string>> findDuplicate(vector<string> &paths)
    {
        vector<vector<string>> answer;
        vector<vector<string>> filesPath;
        vector<string> filesContent;
        // unordered_set<string> stringSet; // Imprement unordered_set 
        int numberOfcontent = 0;
        for (auto it = paths.begin(); it != paths.end(); ++it)
        {
            // cout << "-------------------------------------" << endl
            //      << *it << std::endl;

            // constructing stream from the string
            stringstream ss(*it);
            vector<string> v;

            int index = 0;
            string Dir_path = "";
            while (getline(ss, *it, ' '))
            {
                if (index == 0)
                {
                    Dir_path = *it;
                }
                else
                {
                    string filenameAndContent = *it;
                    string word;
                    string Cur_filePath, Cur_fileContent;

                    stringstream ss2(filenameAndContent);
                    int index = 0;
                    while (getline(ss2, word, '('))
                    {
                        if (index == 0)
                        { // set file path
                            Cur_filePath = Dir_path + "/" + word;
                            // cout << Cur_filePath << endl;
                        }
                        else
                        { // check file content
                            word.pop_back();
                            auto find_obj = find(filesContent.begin(), filesContent.end(), word);
                            if (find_obj != filesContent.end()) // check that content already added to vector
                            {
                                int index = find_obj - filesContent.begin();
                                filesPath[index].push_back(Cur_filePath);
                            }
                            else
                            {
                                filesContent.push_back(word);
                                filesPath.push_back({Cur_filePath});
                                numberOfcontent++;
                            }
                        }
                        index++;
                    }
                }
                index++;
            }
        }
        
        // // This sectoin of code have timeout problem
        // for (auto it = filesPath.begin(); it != filesPath.end(); ++it)
        // {
        //     vector<string> temp{*it};
        //     if(temp.size() > 1){
        //         cout << temp.size() << endl;
        //         answer.push_back(temp);
        //     }
        // }

        // Collect only the file paths with duplicate content
        for (const auto &entry : filesPath)
        {
            if (entry.size() > 1)
            {
                answer.push_back(entry);
            }
        }

        print2dvec(answer);
        return answer;
    }
};
48985