242. Valid Anagram - C

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

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

Example 2:

Input: s = "rat", t = "car"
Output: false

Answer 1: Time Limit Exceeded

bool isAnagram(char * s, char * t){
    bool result;    // 사용X
    int i, j;
    int isSame = 0; // s와 t가 같은지 알려주는 변수
    int *idx = (int *)malloc(strlen(s)*sizeof(int));
    // t의 인덱스들(0~strlen(t)-1)을 저장하여 s와 같은 알파벳이 나왔을 경우 값을 -1로 변경
    // anagram일 경우 모든 값들이 -1이 될 것임
    
    // 두 문자열의 길이가 다를 경우 무조건 false
    if(strlen(s) != strlen(t))
    {
        return false;
    }
    
    // idx에 t와 같은 길이의 인덱스들 저장
    for(i=0;i<strlen(s);i++)
    {
        idx[i] = i;
    }
    
    // s, t 비교
    for(i=0;i<strlen(s);i++)
    {
        for(j=0;j<strlen(t);j++)
        {
            // 이미 s와 같았던 전적이 있으면 if문 통과 X
            if(s[i] == t[j] && idx[j] != -1)
            {
                isSame = 1;
                idx[j] = -1;
                break;
            }
        }
        
        // t의 알파벳 중 s와 같은 알파벳이 하나라도 없을 경우
        if(isSame == 0)
        {
            return false;
        }
        
        // isSame 초기화
        isSame = 0;
    }
    
    // 하나라도 -1 아닌 값이 있으면 anagram이 아니므로 false
    for(i=0;i<strlen(s);i++)
    {
        if(idx[i] != -1)
        {
            return false;
        }
    }
    
    return true;
}

내가 봐도 for문 남발에 넘 비효율적 코드

Answer 2: Accepted

void getFreqCounter(char *arr, int *freqCounter){
    int i = 0;
    
    // 핵심 !!
    // 특정 알파벳이 몇번 등장했는지 count
    while(arr[i] != '\0') {
        freqCounter[arr[i] - 'a']++;
        i++;
    }
    return;
}

bool isAnagram(char * s, char * t){
    if(s == NULL || t == NULL)
        return false;
    
    if(strlen(s) != strlen(t)) 
        return false;
    
    int freqCounterS[26] = {0};
    getFreqCounter(s, freqCounterS);
    
    int freqCounterT[26] = {0};
    getFreqCounter(t, freqCounterT);
    
    /* Compare freqCounter*/
    for(int i = 0; i < 26; i++) {
        if(freqCounterS[i] != freqCounterT[i])
            return false;
    }
    return true;
}

Discuss에 있던 C Solution using freq counter

• freqCounter가 인덱스와 비슷한 역할을 한다고 생각..
• 특정 알파벳이 몇번 등장했는지 비교를 통한 수행
• 알파벳은 총 26개 이므로 배열의 크기도 26으로 제한 => 메모리도 효율적