1202. Smallest String With Swaps

https://leetcode.com/problems/smallest-string-with-swaps/

Smallest String With Swaps - LeetCode

 

 문자열에서 주어진 pair에 들어있는 index들을 스왑하는데, 해당 경우의 수 중 lexiographically하게 가장 작은 문자열을 구하는 문제다.  

 

class Solution {
public:
    vector<int> indices;
    string indiceStr;
    vector<bool> visited;
    vector<vector<int>> adj;
    
    void dfs(string &s, int pos){
        visited[pos] = true;
        
        indiceStr += s[pos];
        indices.push_back(pos);
        
        for(int &i : adj[pos]){
            if(visited[i]) continue;
            dfs(s, i);
        }
    }
    
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.size();
        
        visited.resize(n, false);
        adj.resize(n);
        
        for(auto pair : pairs){
            int v1 = pair[0];
            int v2 = pair[1];
            
            adj[v1].push_back(v2);
            adj[v2].push_back(v1);
        }
        
        for(int i = 0; i < n; i++){
            if(visited[i]) continue;
            
            indiceStr = "";
            indices.clear();
            dfs(s, i);
            sort(indiceStr.begin(), indiceStr.end());
            sort(indices.begin(), indices.end());
            
            int m = indices.size();
            
            for(int i = 0; i < m; i++){
                s[indices[i]] = indiceStr[i];
            }
        }
        return s;
    }
};

"cba" [[0,1],[1,2]] 이러한 example이 있는 경우, [0, 1]을 스왑하면 "bca", [1, 2]를 스왑하면 "bac"이다.  그런데 [1, 2]를 먼저 스왑하고 [0, 1]을 스왑하면 "abc"가 되므로 lexiographically 하게 작은 값은 "abc"가 된다.  즉, 이전의 순서가 현재의 값에 영향을 준다.

 

 graph적으로 주어진 문제를 본다면 pair가 edge가 된다.  0~n까지 node라고 가정할 때, pair로 연결되어있는 값들은 하나의 그룹을 이룬다.

 

[[0,3],[1,2],[0,2], [4, 5], [5, 6]] 의 예시를 보면 [0, 1, 2, 3]과 [4, 5, 6]이 각각 그룹(그래프)를 이루고 있음을 알 수 있다.  해당 그룹 안에서는 모두 스왑이 가능하다.  즉, 해당 그룹에서 값들을 정렬해서 저장해주면 정답이 된다는 뜻이다.

 

Time complexity: O(N * g log g)

Space complexity: O(N)