finding if two words are anagrams of each other

Question

I am looking for a method to find if two strings are anagrams of one another.

Ex: string1 - abcde
string2 - abced
Ans = true
Ex: string1 - abcde
string2 - abcfed
Ans = false

the solution i came up with so for is to sort both the strings and compare each character from both strings till the end of either strings.It would be O(logn).I am looking for some other efficient method which doesn't change the 2 strings being compared

Answer 1

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).

Answer 2

Get table of prime numbers, enough to map each prime to every character. So start from 1, going through line, multiply the number by the prime representing current character. Number you'll get is only depend on characters in string but not on their order, and every unique set of characters correspond to unique number, as any number may be factored in only one way. So you can just compare two numbers to say if a strings are anagrams of each other.

Unfortunately you have to use multiple precision (arbitrary-precision) integer arithmetic to do this, or you will get overflow or rounding exceptions when using this method.
For this you may use libraries like BigInteger, GMP, MPIR or IntX.

Pseudocode:

prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101}  primehash(string)     Y = 1;     foreach character in string         Y = Y * prime[character-'a']      return Y  isanagram(str1, str2)     return primehash(str1)==primehash(str2) 

Answer 3

1. Create a Hashmap where key - letter and value - frequencey of letter,
2. for first string populate the hashmap (O(n))
3. for second string decrement count and remove element from hashmap O(n)
4. if hashmap is empty, the string is anagram otherwise not.

Answer 4

The steps are:

1. check the length of of both the words/strings if they are equal then only proceed to check for anagram else do nothing
2. sort both the words/strings and then compare

JAVA CODE TO THE SAME:

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package anagram;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 *
 * @author Sunshine
 */
public class Anagram {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        // TODO code application logic here
        System.out.println("Enter the first string");
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine().toLowerCase();
        System.out.println("Enter the Second string");
        BufferedReader br2 = new BufferedReader(new InputStreamReader(System.in));
        String s2 = br2.readLine().toLowerCase();
        char c1[] = null;
        char c2[] = null;
        if (s1.length() == s2.length()) {


            c1 = s1.toCharArray();
            c2 = s2.toCharArray();

            Arrays.sort(c1);
            Arrays.sort(c2);

            if (Arrays.equals(c1, c2)) {
                System.out.println("Both strings are equal and hence they have anagram");
            } else {
                System.out.println("Sorry No anagram in the strings entred");
            }

        } else {
            System.out.println("Sorry the string do not have anagram");
        }
    }
}