力扣算法-Day12

242.有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例?1: 输入: s = "anagram", t = "nagaram" 输出: true

示例 2: 输入: s = "rat", t = "car" 输出: false

说明:?你可以假设字符串只包含小写字母。

思路：

? ? ? ? 排序：t 是 s的异位词等价于「两个字符串排序后相等」。因此我们可以对字符串 s?和 t分别排序，看排序后的字符串是否相等即可判断。此外，如果 s和 t?的长度不同，t 必然不是 s的异位词。

????????哈希表：数组就是一个简单的哈希表。而且这道题目中字符串只有小写字符，那么就可以定义一个大小为26的数组，来记录字符串s、t里字符出现的次数。s中字符出现一次，对应的索引++；t中字符出现一次，对应的索引--；

那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

qsort函数的原型定义在stdlib.h头文件中，如果要使用qsort函数，需要在程序中首先包含这个头文件。在对数组排序时，只需调用qsort函数并传递需要排序的数组、元素个数、元素大小和比较函数即可。

qsort函数的原型定义：

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void *));

其中，参数的含义如下：

• base：指向待排序的数组首地址。
• nitems：数组的元素个数。
• size：每个元素的大小。
• compar：用来比较两个元素的函数指针。

排序：

int cmp(const void* _a, const void* _b) {
    char a = *(char*)_a, b = *(char*)_b;
    return a - b;
}

bool isAnagram(char* s, char* t) {
    int len_s = strlen(s), len_t = strlen(t);
    if (len_s != len_t) {
        return false;
    }
    qsort(s, len_s, sizeof(char), cmp);
    qsort(t, len_t, sizeof(char), cmp);
    return strcmp(s, t) == 0;
}

哈希表：

bool isAnagram(char* s, char* t) {
    //判断长度是否相同
    if (strlen(s) != strlen(t)) {
        return false;
    }
    //定义一个哈希表，初始化为0
    int same[26] = {0};
    for ( int i=0; i<strlen(s); i++) {
        same[s[i] - 'a']++;
        same[t[i] - 'a']--;
    }
    //判断元素个数是否相同
    for ( int i=0; i<26; i++) {
        if (same[i] != 0) {
            return false;
        }
    }
    return true;
}

这一期专栏记录将我每天的刷题，希望各位的监督，也希望和各位共勉。

追光的人，终会光芒万丈！！