一、问题描述

我们面对的问题是处理一个下标从 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 < j
    for (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;
}

四、代码解释

isSimilar 函数

• 该函数接受两个字符串指针 str1 和 str2 作为参数，用于判断它们是否相似。
• charSet1 和 charSet2 是长度为 26 的整数数组，初始值都为 0。
• 第一个 for 循环遍历 str1，将 str1 中出现的字符对应的数组元素置为 1。
• 第二个 for 循环遍历 str2，同样将 str2 中出现的字符对应的数组元素置为 1。
• 最后一个 for 循环比较两个数组的对应元素，如果有不同的元素，则返回 false；如果所有元素都相同，则返回 true。

similarPairs 函数

• 该函数接受一个字符串数组 words 和数组的大小 wordsSize 作为参数，返回相似字符串对的数量。
• pairCount 是一个计数器，用于记录相似字符串对的数量。
• 外层 for 循环控制 i，内层 for 循环控制 j，并且 j 从 i + 1 开始，保证 j > i。
• 对于每一对字符串 words[i] 和 words[j]，调用 isSimilar 函数进行判断，如果相似，则 pairCount 加 1。
• 最后返回 pairCount。

main 函数

• 定义了一个字符串数组 words，并计算其大小 wordsSize。
• 调用 similarPairs 函数计算相似字符串对的数量，并将结果存储在 result 中。
• 使用 printf 函数输出结果。

五、复杂度分析

时间复杂度

时间复杂度为，其中 n 是字符串数组的长度，m 是字符串的平均长度。这是因为我们需要使用两层嵌套循环遍历所有的字符串对，对于每一对字符串，还需要遍历它们的每个字符来判断是否相似。

空间复杂度

空间复杂度为，因为只使用了常数大小的额外空间。具体来说，isSimilar 函数中使用的两个长度为 26 的数组 charSet1 和 charSet2 的大小是固定的，不随输入规模的变化而变化。