TikTok OA 面试真题解析：Similar Strings 相似字符串计数

Two strings are said to be similar if they are composed of the same characters.

For example, "abaca" and "cba" are similar since both of them are composed of characters 'a', 'b', and 'c'. However, "abaca" and "bcd" are not similar since they do not share all of the same letters.

Given an array of strings words of length n, find the number of pairs of strings that are similar.

Note:

• Each string is composed of lowercase English characters only.
• Pairs are considered index-wise, i.e., two equal strings at different indices are counted as separate pairs.
• A pair at indices (i, j) is the same as the pair at (j, i).

Example

Consider n = 3, words = ["xyz", "foo", "of"].

Here, the strings "foo" and "of" are similar because they are composed of the same characters ['o', 'f']. There are no other similar pairs, so the answer is 1.

Function Description

Complete the function countSimilarPairs in the editor below.

countSimilarPairs has the following parameter:

• string words[n]: an array of n strings

Returns

• long int: the number of similar pairs

这道题的核心是把每个字符串转换成“字符集合签名”：只要两个字符串包含的字母种类完全相同，就算相似。由于字符串只包含小写英文字母，可以用 26 位位掩码或排序去重后的字符串作为 key；遍历 words 时统计每种签名出现次数，再累加组合数 C(cnt, 2) 即可。这样既能正确处理相同字符串在不同下标处算不同配对，也能满足 n 和总字符长度都较大的限制。