LeetCode 2506 统计相似字符串对的数目

一、问题描述

我们面对的问题是处理一个下标从 0 开始的字符串数组 words。题目中定义了一种字符串相似的规则：如果两个字符串由相同的字符组成，那么就认为这两个字符串是相似的。例如，"abca" 和 "cba" 是相似的，因为它们都由字符 'a'、'b'、'c' 组成；而 "abacba" 和 "bcfd" 不相似，因为它们不是由相同字符组成的。我们的任务是找出满足字符串 words[i] 和 words[j] 相似的下标对 (i, j) 的数目，其中 0 <= i < j <= words.length - 1。

二、解题思路

要解决这个问题，我们可以分两步走。第一步，需要一个函数来判断两个字符串是否相似；第二步，遍历字符串数组中的所有字符串对，统计相似字符串对的数量。

判断字符串是否相似

为了判断两个字符串是否由相同的字符组成，我们可以使用一个长度为 26 的数组来记录每个字符是否在字符串中出现过。因为英文字母一共有 26 个，我们可以将每个字符映射到数组的一个位置上。对于每个字符串，遍历其每个字符，将对应位置的数组元素置为 1。最后比较两个数组，如果所有对应位置的元素都相同，那么这两个字符串就是相似的。

统计相似字符串对的数量

使用两层嵌套循环遍历字符串数组，外层循环控制 i，内层循环控制 j，并且保证 j > i。对于每一对字符串，调用判断相似性的函数，如果它们相似，就将计数器加 1。

三、代码实现

#include <stdio.h>
#include <string.h>
#include <stdbool.h>// 检查两个字符串是否由相同字符组成（相似）
bool isSimilar(const char* str1, const char* str2) {int charSet1[26] = {0};int charSet2[26] = {0};// 遍历第一个字符串，标记出现过的字符for (int i = 0; str1[i] != '\0'; i++) {charSet1[str1[i] - 'a'] = 1;}// 遍历第二个字符串，标记出现过的字符for (int i = 0; str2[i] != '\0'; i++) {charSet2[str2[i] - 'a'] = 1;}// 比较两个字符集合是否相同for (int i = 0; i < 26; i++) {if (charSet1[i] != charSet2[i]) {return false;}}return true;
}int similarPairs(char** words, int wordsSize) {int pairCount = 0;// 双重循环遍历所有可能的字符串对 (i, j)，其中 i < jfor (int i = 0; i < wordsSize; i++) {for (int j = i + 1; j < wordsSize; j++) {if (isSimilar(words[i], words[j])) {pairCount++;}}}return pairCount;
}int main() {char* words[] = {"abca", "cba", "abacba", "bcfd"};int wordsSize = sizeof(words) / sizeof(words[0]);int result = similarPairs(words, wordsSize);printf("满足条件的下标对数目为: %d\n", result);return 0;
}