diff options
Diffstat (limited to 'other/smallest_string_swaps.cpp')
-rw-r--r-- | other/smallest_string_swaps.cpp | 55 |
1 files changed, 0 insertions, 55 deletions
diff --git a/other/smallest_string_swaps.cpp b/other/smallest_string_swaps.cpp deleted file mode 100644 index c521309..0000000 --- a/other/smallest_string_swaps.cpp +++ /dev/null @@ -1,55 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - vector<int> parent; - string smallestStringWithSwaps(string s, vector<vector<int>> &pairs) { - parent.resize(s.length()); - map<int, set<int>> obj; - set<int> idx; - string ans = s; - for (int i = 0; i < parent.size(); i++) - parent[i] = i; - for (int i = 0; i < pairs.size(); i++) { - int u = pairs[i][0]; - int v = pairs[i][1]; - int fx = findParent(u); - int fy = findParent(v); - if (fx != fy) - parent[fy] = fx; - } - for (int i = 0; i < pairs.size(); i++) { - int u = pairs[i][0]; - int v = pairs[i][1]; - int fx = findParent(u); - obj[fx].insert(u); - obj[fx].insert(v); - } - for (auto it = obj.begin(); it != obj.end(); it++) { - idx = it->second; - vector<pair<char, int>> t; - auto index = idx.begin(); - for (index = idx.begin(); index != idx.end(); index++) { - int pos = *index; - char ch = s[pos]; - t.push_back({ch, pos}); - } - sort(t.begin(), t.end()); - index = idx.begin(); - for (int i = 0; i < t.size(); i++) { - ans[*index] = t[i].first; - index++; - } - } - return ans; - } - -private: - int findParent(int n) { - if (parent[n] == n) - return n; - return parent[n] = findParent(parent[n]); - } -}; - -int main() {} |