一、题目

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

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

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

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

进阶:如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?


二、解法

方法1:排序

算法:通过将 s 的字母重新排列成 t 来生成变位词。因此,如果 T 是 S 的变位词,对两个字符串进行排序将产生两个相同的字符串。此外,如果 s 和 t 的长度不同,t 不能是 s 的变位词,我们可以提前返回。
代码如下

void swap(char* a, char* b)
{
    char tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void strSort(char* str)
{
    int len = strlen(str);
    char* pf = str;

    for (int i = 0; i < len - 1; i++)
    {
        for (int j = 0; j < len - i - 1; j++)
        {
            if (*(pf+j) > *(pf+j+1))            
                swap(pf + j, pf + j + 1);           
        }        
    }
    puts(str);
}

bool isAnagram(char* s, char* t)
{
    int s_len = strlen(s);
    int t_len = strlen(t);
    if (s_len != t_len)
        return false;
    strSort(s);
    strSort(t);
    if (strcmp(s, t) == 0)
        return true;
    else
        return false;
}

上述代码是没有问题的,但是提交时却给出了“超出时间限制”错误提示,如下图所示。

确实,上述算法本身没问题,出问题的应该是排序算法,由于使用的冒泡排序,使得时间复杂度达到O(n2)O(n^2),因此考虑采用效率更高的归并排序。为什么选用归并而不是选择排序呢?因为归并排序的性能不受输入数据的影响,并且表现比选择排序好的多,因为归并始终都是 O(nlogn)O(nlogn) 的时间复杂度。而代价则是需要额外的内存空间。(注:关于归并排序算法的相关介绍,请出门左转看我下篇论述
采用归并排序后的代码如下(通过):

int min(int a, int b)
{
    return a < b ? a : b;
}

void merge_sort(char* str)
{
    int len = strlen(str);
    char* ptr = str;
    char* newStr = (char*)malloc(len * sizeof(char));

    for (int seg = 1; seg < len; seg += seg)
    {
        for (int start = 0; start < len; start += seg * 2)
        {
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)            
                newStr[k++] = (ptr[start1] < ptr[start2]) ? ptr[start1++] : ptr[start2++];       
            
            while (start1 < end1)
                newStr[k++] = ptr[start1++];

            while (start2 < end2)
                newStr[k++] = ptr[start2++];
        }
        char* temp = ptr;
        ptr = newStr;
        newStr = temp;
    }
    if (ptr != str)
    {
        for (int i = 0; i < len; i++)
            newStr[i] = ptr[i];
        newStr = ptr;
    }
    free(newStr);
}

bool isAnagram(char* s, char* t)
{
    int s_len = strlen(s);
    int t_len = strlen(t);
    if (s_len != t_len)
        return false;
    merge_sort(s);
    // puts(s);
    merge_sort(t);
    if (strcmp(s, t) == 0)
        return true;
    else
        return false;
}

emmm……虽然通过了,但是结果好像并不感人啊

尤其是内存占用,简直了!

没有比这个更糟糕的了。当然了,大家也可以用快排来做,但是结果应该不会很理想。

那有没有更好地方法呢?
答案是:有的!

方法2:哈希表(模拟实现)

思路

  • 首先判断两个字符串长度是否相等,不相等则直接返回 false
  • 若相等,则初始化 26 个字母哈希表,遍历字符串 s 和 t
  • s 负责在对应位置增加,t 负责在对应位置减少
  • 如果哈希表的值都为 0,则二者是字母异位词

代码如下:

bool isAnagram(char* s, char* t)
{
    int s_len = strlen(s);
    int t_len = strlen(t);
    if (s_len != t_len)
        return false;
    int alpha[26] = { 0 };
    for (int i = 0; i < s_len; i++)
    {
        alpha[s[i] - 'a']++;
        alpha[t[i] - 'a']--;
    }
    for (int i = 0; i < 26; i++)
    {
        if (alpha[i] != 0)
            return false;
    }
    return true;
}

复杂度分析

  • 时间复杂度:O(n)O(n)。时间复杂度为 O(n)O(n) 因为访问计数器表是一个固定的时间操作。
  • 空间复杂度:O(1)O(1)。尽管我们使用了额外的空间,但是空间的复杂性是 O(1)O(1),因为无论 N 有多大,表的大小都保持不变。