[Solution] 893. Groups of Special-Equivalent Strings

Difficulty: Easy

Problem

You are given an array A of strings.

Two strings S and T are special-equivalent if after any number of moves, S == T.

A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].

Now, a group of special-equivalent strings from A is a non-empty subset S of A such that any string not in S is not special-equivalent with any string in S.

Return the number of groups of special-equivalent strings from A.

Example 1:

Input: ["a", "b", "c", "a", "c", "c"]

Output: 3

Explanation: 3 groups ["a", "a"], ["b"], ["c", "c", "c"]

Example 2:

Input: ["aa", "bb", "ab", "ba"]

Output: 4

Explanation: 4 groups ["aa"], ["bb"], ["ab"], ["ba"]

Example 3:

Input: ["abc", "acb", "bac", "bca", "cab", "cba"]

Output: 3

Explanation: 3 groups ["abc", "cba"], ["abc", "bca"], ["bac", "cab"]

Example 4:

Input: ["abcd", "cdab", "adcb", "cbad"]

Output: 1

Explanation: 3 groups ["abcd", "cdab", "adcb", "cbad"]

Note:

1 <= A.length <= 1000
1 <= A[i].length <= 20
All A[i] have the same length.
All A[i] consist of only lowercase letters.

Solution

统计每个字符串奇数位和偶数位上的字频，当两个字符串以此法统计的字频分布相同时，称这两个字符串为 special-equivalent。我的代码写得似乎麻烦了点，以后补充更简便的写法。

class CharCounter

{

    private SortedDictionary<char, int> counter;

    public CharCounter(string str)

    {

        counter = new SortedDictionary<char, int>();

        bool isOdd = false;

        foreach(char c in str)

        {

            if(isOdd)

            {

                if (counter.ContainsKey(char.ToUpper(c)))

                    ++counter[char.ToUpper(c)];

                else

                    counter.Add(char.ToUpper(c), 1);

            }

            else

            {

                if (counter.ContainsKey(c))

                    ++counter[c];

                else

                    counter.Add(c, 1);

            }

            isOdd = !isOdd;

        }

    }

    public override string ToString()

    {

        StringBuilder builder = new StringBuilder("{");

        foreach(var pair in counter)

        {

            builder.Append($"'{pair.Key}':{pair.Value},");

        }

        builder.Remove(builder.Length - 1, 1);

        builder.Append("}");

        return builder.ToString();

    }

    public override bool Equals(object obj)

    {

        return ToString() == obj.ToString();

    }

    public override int GetHashCode()

    {

        return ToString().GetHashCode();

    }

}

public class Solution

{

    public int NumSpecialEquivGroups(string[] A)

    {

        return (from str in A select new CharCounter(str)).ToHashSet().Count;

    }

}

巴特西