hogecoder

tsutaj 競技プログラミングの記録

LeetCode Biweekly Contest 6: String Transforms Into Another String

問題概要

原文 → Loading...

文字列  s1 s2 が与えられる。

以下の操作を 0 回以上行うことによって、 s1 s2 と一致させることができるか判定せよ。

  • アルファベットをふたつ選び、それを  x, y とする。 s1 に含まれる全ての  x を同時に  y へ変更する。

解説

操作をグラフとしてみることを考える。より具体的には、「 x y に変更する」という操作を、 x から  y への有向辺としてとらえる。

まず、それぞれの頂点に対して、出る辺が 2 つ以上存在するときは不可能である。同じアルファベットを異なる複数のアルファベットに変更することができないからである。

不可能なパターンはもう 1 つあり、それは「すべての頂点がなんらかの閉路に含まれている」ときである。

そもそもこの有向グラフは操作すべき順番を与えてくれるものであって (x → y → z というグラフがあるなら、y を z に変えた後に x を y に変えなければならない)、閉路に含まれる頂点でないならこのルールに従えば条件通りに操作可能であるが、閉路に含まれる場合は依存関係が循環しているのでもう少し工夫がいる。どの閉路にも含まれない頂点が存在するとき、そのいずれかは入次数が 0 (つまり操作後に空き状態になる) であるから、それをうまく使えば閉路を壊すことができる。ただしそのような頂点がない場合は閉路が壊せないので、条件を満たすことができなくなる。

実装によっては  s1 s2 がはじめから一致している場合がコーナーになりうるので注意。

class Solution {
public:
    bool canConvert(string str1, string str2) {
        const int N = 26;
        int L = str1.size();
        if(str1 == str2) return true;
        
        vector<int> indeg(N), outdeg(N);
        int edge[N][N] = {};
        vector< vector<int> > G(N);
        for(int i=0; i<L; i++) {
            int u = str1[i] - 'a';
            int v = str2[i] - 'a';
            if(edge[u][v]) continue;
            edge[u][v] = true;
            G[u].emplace_back(v);
            indeg[v]++;
            outdeg[u]++;
        }
        
        // outdeg
        for(int i=0; i<N; i++) if(outdeg[i] >= 2) return false;
        
        // exist non-loop vertex
        queue<int> que;
        
        bool non_loop = false;
        for(int i=0; i<N; i++) {
            if(indeg[i] == 0) {
                non_loop = true;
                que.emplace(i);
            }
        }
        while(que.size()) {
            int cur = que.front(); que.pop();
            for(auto to : G[cur]) {
                if(--indeg[to] == 0) {
                    non_loop = true;
                    que.emplace(to);
                }
            }
        }
        
        if(!non_loop) return false;
        return true;
    }
};

こういうの一発で通せるようになりたいですね。