[leetcode/lintcode 題解] 算法面試真題詳解：特殊等價字元串組

描述

你将得到一個字元串數組 A。

如果經過任意次數的移動，S == T，那麼兩個字元串 S 和 T 是特殊等價的。

一次移動包括選擇兩個索引 i 和 j，且 i ％ 2 == j ％ 2，交換 S[j] 和 S [i]。

現在規定，A 中的特殊等價字元串組是 A 的非空子集 S，這樣不在 S 中的任何字元串與 S 中的任何字元串都不是特殊等價的。

傳回 A 中特殊等價字元串組的數量。

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

線上評測位址：

領扣題庫官網

樣例1
示例 1：

輸入：["a","b","c","a","c","c"]
輸出：3
解釋：3 組 ["a","a"]，["b"]，["c","c","c"]           

樣例2
示例 2：

輸入：["aa","bb","ab","ba"]
輸出：4
解釋：4 組 ["aa"]，["bb"]，["ab"]，["ba"]           

樣例3
示例 3：

輸入：["abc","acb","bac","bca","cab","cba"]
輸出：3
解釋：3 組 ["abc","cba"]，["acb","bca"]，["bac","cab"]           

樣例4
示例 4：

輸入：["abcd","cdab","adcb","cbad"]
輸出：1
解釋：1 組 ["abcd","cdab","adcb","cbad"]           

題解

class Solution {
    /**
     * @param A: a string array
     * @return: Return the number of groups of special-equivalent strings from A.
     */
    public int numSpecialEquivGroups(String[] A) {
        // write your code here
        Set<String> s = new HashSet();
        for (String str: A) {
            int[] count = new int[52];
            for (int i = 0; i < str.length(); ++i)
                count[str.charAt(i) - 'a' + 26 * (i % 2)]++;
            s.add(Arrays.toString(count));
        }
        return s.size();
    }
}           

更多題解參考：

九章官網solution