Using merge sort in C, 36ms


  • 0
    C
    void mergeSort(char *str, char *tmp, int left, int right)
    {
        int mid;
        int i, j, k;
    
        if (left >= right) return;
    
        mid = (left + right) / 2;
        mergeSort(str, tmp, left, mid);
        mergeSort(str, tmp, mid + 1, right);
    
        i = left;
        j = mid + 1;
        k = i;
    
        while (i <= mid && j <= right) {
            if (str[i]  < str[j])
                tmp[k++] = str[i++];
            else tmp[k++] = str[j++];
        }
    
        while (i <= mid) tmp[k++] = str[i++];
        while (j <= right) tmp[k++] = str[j++];
    
        /* copy sorted sequence back */
        for (k = left ; k <= right ; ++k)
            str[k] = tmp[k];
    }
    
    bool isAnagram(char *s, char *t)
    {
        int     i;
        int     l;
        char    *tmp;
    
        if ((l = strlen(s)) != strlen(t)) return 0;
    
        tmp = malloc(l * sizeof(char));
        mergeSort(s, tmp, 0, l - 1);
        mergeSort(t, tmp, 0, l - 1);
    
        for (i = 0 ; i < l ; ++i)
            if (s[i] != t[i]) return 0;
    
        return 1;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.