Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【LeetCode No.1201 Smallest String With Swaps】スワップ可能なグループは任意の並びを作ることが可能

これどっかで見たことあると思ったんだけど、どこだったでしょうか。

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

問題

文字列と、インデックスのペアの列が与えられる。

ペアの中のスワップをどんな順番で何度でもして良いとして、辞書順最小の文字列を作りなさい。

方針

例えば、(0,1),(1,2)というペアがあった場合、012のどんな並び順も作れるっぽいことに気づくことが必要。実装では、Union Findを使って連結成分を調べればよい。

いい機会なので、簡単な証明をしておく。

f:id:akiradeveloper529:20190922162806j:plain

まず、上図のように一直線に並んでる場合を考える。任意の並び順は一番後ろのものから決めていくことで作ることが出来る。

次に、下図のように3つの直線が1つのハブXを介して分岐している場合を考える。すると、Xを介して直線間で数を交換することが出来る。従って、任意の並び順を作ることが出来る。

実装

fn solve(s: Vec<char>, pairs: Vec<(usize,usize)>) -> String {
    let mut s = s;
    let mut n = s.len();
    let mut uf = UnionFind::new(n);
    for (u,v) in pairs {
        uf.merge(u, v);
    }
    let mut groups = HashMap::new();
    for u in 0..n {
        groups.entry(uf.root(u)).or_insert(vec![]).push(u);
    }

    for group in groups.values() {
        let mut tmp = vec![];
        let mut group = group.clone();
        let m = group.len();
        group.sort();
        for &i in &group {
            tmp.push(s[i]);
        }
        tmp.sort();
        for i in 0..m {
            s[group[i]] = tmp[i];
        }
    }

    let mut res = String::new();
    for i in 0..n {
        res.push(s[i]);
    }
    res
}