diff options
Diffstat (limited to 'smallest_string_swaps.cpp')
-rw-r--r-- | smallest_string_swaps.cpp | 55 |
1 files changed, 55 insertions, 0 deletions
diff --git a/smallest_string_swaps.cpp b/smallest_string_swaps.cpp new file mode 100644 index 0000000..c521309 --- /dev/null +++ b/smallest_string_swaps.cpp @@ -0,0 +1,55 @@ +#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() {} |