Problem¶

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Constraints:

1 <= s.length, t.length <= 5 * 104
s and t consist of lowercase English letters.

Example 1:

**Input:** s = "anagram", t = "nagaram"
**Output:** true

Solve¶

Sort and compare using hash¶

Re-arrange both string with sort or count each character them comparing.
I prefer Re-arrange as it has the lowest memory

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

I want to implement C code that using similar approach. C not have provided hash function so we use a implement of djb2 hash

// djb2 hash function for strings
unsigned long hash_string(const char* str) {
    unsigned long hash = 5381;
    int c;

    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }

    return hash;
}

int compare_char(const void* a, const void* b) {
    return *(char*)a - *(char*)b;
}

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

    qsort(s, len_s, sizeof(char), compare_char);
    qsort(t, len_t, sizeof(char), compare_char);

    return hash_string(s) == hash_string(t);
}

Counting¶

While this isn’t a general way, we only have a range of 26 character, which quite low, and count sort is a great O(n) way to deal with these type of problem.

int isAnagram(char * s, char * t){
    int lens = strlen(s);

    if (lens != strlen(t)) 
        return 0;

    int s_counter[26] = {0};
    int t_counter[26] = {0};

    for (int i = 0; i < lens; i++){
        int curr_letter_s = s[i] - 97;
        s_counter[curr_letter_s]++;

        int curr_letter_t = t[i] - 97;
        t_counter[curr_letter_t]++;
    }

    for (int i = 0; i < 26; i++){
        if (s_counter[i] != t_counter[i]) return 0;
    }

    return 1;
}

Compare¶

Time Submitted	Status	Runtime	Memory	Language
07/19/2023 22:07	Accepted	6 ms	5.8 MB	c
07/19/2023 22:04	Accepted	30 ms	6.3 MB	c
07/19/2023 21:59	Accepted	71 ms	17.4 MB	python3

Last update : October 13, 2023
Created : August 16, 2023