题目链接

Satisfiability of Equality Equations - LeetCode

注意点

必须要初始化pre

解法

解法一：典型的并查集算法应用。先遍历所有等式，将等号两边的字母加入同一分类，每类中的字母都是相等的。然后遍历不等式，如果不等号两边的字母属于同一类则返回false。时间复杂度O(nm)

class Solution {

public:

    map<char,char> pre;

    char Find(char x)

    {

        char r = x;

        while(pre[r] != r)

        {

            r = pre[r];

        }

        return r;

    }

    void Join(char x,char y)

    {

        char fx = Find(x);

        char fy = Find(y);

        if(fx != fy) pre[fx] = fy;

    }

    void Init()

    {

        char letter[26] ={'a','b','c','d','e','f','g','h','i',

                          'j','k','l','m','n','o','p','q','r',

                          's','t','u','v','w','x','y','z'};

        for (auto l:letter)

        {

            pre[l] = l;

        }

    }

    bool equationsPossible(vector<string>& equations) {

        Init();

        for(auto e:equations)

        {

            if(e[1] == '=') Join(e[0],e[3]);

        }

        for(auto e:equations)

        {

            if(e[1] == '!' && Find(e[0]) == Find(e[3]))

            {

                return false;

            }

        }

        return true;

    }

};

小结

快速搞定并查集算法

巴特西

Satisfiability of Equality Equations - LeetCode

题目链接

注意点

解法

小结

最新文章

热门文章