How to Check If Two Words Are Anagrams

How to check if two words are anagrams

Fastest algorithm would be to map each of the 26 English characters to a unique prime number. Then calculate the product of the string. By the fundamental theorem of arithmetic, 2 strings are anagrams if and only if their products are the same.

finding if two words are anagrams of each other

Count the frequency of each character in the two strings. Check if the two histograms match. O(n) time, O(1) space (assuming ASCII) (Of course it is still O(1) space for Unicode but the table will become very large).

Check if two words are anagram in C

qsort is your friend! Why reinvent the wheel? The stdlib provides all means for this task!
Whitespace can easily be stripped after sorting using strcspn, as each of the whitespace chars ascii code is < alnum characters ascii code.
If you don't want to rely on those ascii properties, the compare_chars function can easily adapted so that all whitespace are sorted either to the front or to the end (In the example it sorts the ws to the end).
I wonder if somebody comes up with a unicode version of isAnagram.
Please note that i applied the sorting on a copy of the original strings so that the isAnagram function does not mess up the input.

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

int compare_chars(const void *c1, const void *c2)
{
    // Sign corresponds to backward sorting so that
    // whitespace appears at the end
    return *(char *)c2 - *(char *)c1;
}

void sort_remove_whitespace(const char *src, char dest[strlen(src) + 1])
{
    strcpy(dest, src);
    qsort(dest, strlen(dest), sizeof(char), compare_chars);
    dest[strcspn(dest, " \b\t\v\r\n")] = '\0';
}

bool isAnagram(char* T1, char *T2)
{
    char T1_copy[strlen(T1) + 1];
    char T2_copy[strlen(T2) + 1];
    
    sort_remove_whitespace(T1, T1_copy);
    sort_remove_whitespace(T2, T2_copy);
    
    printf("T1 sorted: '%s', T2 sorted: '%s'\n", T1_copy, T2_copy);
    
    return 0 == strcmp(T1_copy, T2_copy);
}

void prompt(const char *msg, char *buf, size_t N)
{
    char *fgets_return;

    puts(msg);
    fgets_return = fgets(buf, N, stdin);
    
    if (NULL == fgets_return)
    {
        printf("Input error!");
        exit(-1);               // fail fast fail early
    }
    
    printf("OK. Got %s\n", buf);
}

int main()
{
    char T1[100], T2[100];

    prompt("Give the first word :", T1, sizeof(T1));
    prompt("Give the second word :", T2, sizeof(T2));

    if ( isAnagram(T1, T2) )
    {
        printf("The two words are Anagrams !\n");
    }
    else
    {
        printf("The two words are not Anagrams !\n");
    }

    return 0;
}

Example output:

Give the first word :
dead beef
OK. Got dead beef

Give the second word :
fat thief
OK. Got fat thief

T1 sorted: 'feeeddba', T2 sorted: 'ttihffea'
The two words are not Anagrams !

Give the first word :
anagram
OK. Got anagram

Give the second word :
nag a ram
OK. Got nag a ram

T1 sorted: 'rnmgaaa', T2 sorted: 'rnmgaaa'
The two words are Anagrams !

How to check whether two words are anagrams python

Your algorithm is ok. Your problem is that you don't consider upper and lower case letters. Changing the two lines

alist1 = list(deleteSpaces(s1))
alist2 = list(deleteSpaces(s2))

to

alist1 = list(deleteSpaces(s1).lower())
alist2 = list(deleteSpaces(s2).lower())

will solve your issue.
As an alternative you could simply use the following function:

def anagrams(s1, s2):
    def sort(s):
        return sorted(s.replace(" ", "").lower())
    return sort(s1) == sort(s2)

If you want to have a faster solution with complexity of O(n), you should use a Counter instead of sorting the two words:

from collections import Counter

def anagrams(s1, s2):
    def get_counter(s):
        return Counter(s.replace(" ", "").lower())

    return get_counter(s1) == get_counter(s2)

Check if two Strings are Anagrams Without using built-in features that require Import

Generate a HashMap of frequencies of symbols for both given strings.

Then compare the two maps. If they are equal, then the strings are anagrams.

public static boolean isAnagram(String a, String b) {
    return getFrequencies(a).equals(getFrequencies(b));
}

public static Map<Integer, Long> getFrequencies(String str) {
    
    return str.codePoints()
        .boxed()
        .collect(Collectors.groupingBy(
            Function.identity(),
            Collectors.counting()
        ));
}

main()

public static void main(String[] args) {
    System.out.println(isAnagram("hello", "olhel"));
    System.out.println(isAnagram("hello", "olhelq"));
}

Output:

true
false

Without using any packages or imports

There are different possibilities, the optimal choice would depend on the constraints on the strings received as an input.

If we expect that input will contain only letters of the English alphabet, then we could handle this case by populating two arrays of length 26 where each element corresponds to a frequency of a particular letter (as shown in the link provided by @Federico klez Culloca in the comments). To get the result, we can compare these arrays iterating over the indices and checking values at the same index are equal. This algorithm will run in a linear time O(n) (as well as map-based solution shown above).

In case if we can't expect that symbols in the given strings would be in a particular range, then we can extract arrays of characters from both strings, sort them and compare both array character by character. This algorithm will run in a linear-logarithmic time O(n * log n) because it requires sorting. And since we are not allowed to use imports (like Arrays utility class) then we need to implement a linear-logarithmic sorting algorithm (like quicksort or merge-sort) manually.

JavaScript anagram comparison

Instead of comparing letter by letter, after sorting you can join the arrays to strings again, and let the browser do the comparison:

function compare (a, b) {
    var y = a.split("").sort().join(""),
        z = b.split("").sort().join("");
    console.log(z === y
        ? a + " and " + b + " are anagrams!"
        : a + " and " + b + " are not anagrams."
    );
}

Check whether two strings are anagrams

One way to do it is:

s1 = "elbow"
s2 = "below"

is_anagram <- function(s1, s2){
  s1_sorted <- sort(strsplit(s1, "")[[1]])
  s2_sorted <- sort(strsplit(s2, "")[[1]])
  identical(s1_sorted, s2_sorted)
}

#> is_anagram(s1, s2)
#> [1] TRUE

What is an easy way to tell if a list of words are anagrams of each other?

Put all the letters in alphabetical order in the string (sorting algorithm) and then compare the resulting string.

---

Related Topics