How to check if two words are anagrams

Question

I have a program that shows you whether two words are anagrams of one another. There are a few examples that will not work properly and I would appreciate any help, although if it were not advanced that would be great, as I am a 1st year programmer. "schoolmaster" and "theclassroom" are anagrams of one another, however when I change "theclassroom" to "theclafsroom" it still says they are anagrams, what am I doing wrong?

import java.util.ArrayList;
public class AnagramCheck {
    public static void main(String args[]) {
        String phrase1 = "tbeclassroom";
        phrase1 = (phrase1.toLowerCase()).trim();
        char[] phrase1Arr = phrase1.toCharArray();

        String phrase2 = "schoolmaster";
        phrase2 = (phrase2.toLowerCase()).trim();
        ArrayList<Character> phrase2ArrList = convertStringToArraylist(phrase2);

        if (phrase1.length() != phrase2.length()) {
            System.out.print("There is no anagram present.");
        } else {
            boolean isFound = true;
            for (int i = 0; i < phrase1Arr.length; i++) {
                for (int j = 0; j < phrase2ArrList.size(); j++) {
                    if (phrase1Arr[i] == phrase2ArrList.get(j)) {
                        System.out.print("There is a common element.\n");
                        isFound =;
                        phrase2ArrList.remove(j);
                    }
                }
                if (isFound == false) {
                    System.out.print("There are no anagrams present.");
                    return;
                }
            }
            System.out.printf("%s is an anagram of %s", phrase1, phrase2);
        }
    }

    public static ArrayList<Character> convertStringToArraylist(String str) {
        ArrayList<Character> charList = new ArrayList<Character>();
        for (int i = 0; i < str.length(); i++) {
            charList.add(str.charAt(i));
        }
        return charList;
    }
}

Answer 1

Lots of people have presented solutions, but I just want to talk about the algorithmic complexity of some of the common approaches:

• The simple "sort the characters using Arrays.sort()" approach is going to be O(N log N).

• If you use radix sorting, that reduces to O(N) with O(M) space, where M is the number of distinct characters in the alphabet. (That is 26 in English ... but in theory we ought to consider multi-lingual anagrams.)

• The "count the characters" using an array of counts is also O(N) ... and faster than radix sort because you don't need to reconstruct the sorted string. Space usage will be O(M).

• A "count the characters" using a dictionary, hashmap, treemap, or equivalent will be slower that the array approach, unless the alphabet is huge.

• The elegant "product-of-primes" approach is unfortunately O(N^2) in the worst case This is because for long-enough words or phrases, the product of the primes won't fit into a long. That means that you'd need to use BigInteger, and N times multiplying a BigInteger by a small constant is O(N^2).

  For a hypothetical large alphabet, the scaling factor is going to be large. The worst-case space usage to hold the product of the primes as a BigInteger is (I think) O(N*logM).

• A hashcode based approach is usually O(N) if the words are not anagrams. If the hashcodes are equal, then you still need to do a proper anagram test. So this is not a complete solution.

---

I would also like to highlight that most of the posted answers assume that each code-point in the input string is represented as a single char value. This is not a valid assumption for code-points outside of the BMP (plane 0); e.g. if an input string contains emojis.

The solutions that make the invalid assumption will probably work most of the time anyway. A code-point outside of the BMP will represented in the string as two char values: a low surrogate and a high surrogate. If the strings contain only one such code-point, we can get away with treating the char values as if they were code-points. However, we can get into trouble when the strings being tested contain 2 or more code-points. Then the faulty algorithms will fail to distinguish some cases. For example, [SH1, SL1, SH2, SL2] versus [SH1, SL2, SH2, SL1] where the SH<n> and SL<2> denote high and low surrogates respectively. The net result will be false anagrams.

Alex Salauyou's answer gives a couple of solutions that will work for all valid Unicode code-points.

Answer 2

Sorting approach is not the best one. It takes O(n) space and O(nlogn) time. Instead, make a hash map of characters and count them (increment characters that appear in the first string and decrement characters that appear in the second string). When some count reaches zero, remove it from hash. Finally, if two strings are anagrams, then the hash table will be empty in the end - otherwise it will not be empty.

Couple of important notes: (1) Ignore letter case and (2) Ignore white space.

Here is the detailed analysis and implementation in C#: Testing If Two Strings are Anagrams

Answer 3

There are 3 solution i can think of :

1. Using sorting

# O(NlogN) + O(MlogM) time, O(1) space 
def solve_by_sort(word1, word2):
    return sorted(word1) == sorted(word2)

2. Using letter frequency count

# O(N+M) time, O(N+M) space
def solve_by_letter_frequency(word1, word2):
    from collections import Counter
    return Counter(word1) == Counter(word2)

3. Using the concept of prime factorization. (assign primes to each letter)

import operator
from functools import reduce

# O(N) time, O(1) space - prime factorization
def solve_by_prime_number_hash(word1, word2):
    return get_prime_number_hash(word1) == get_prime_number_hash(word2)

def get_prime_number_hash(word):
    letter_code = {'a': 2, 'b': 3, 'c': 5, 'd': 7, 'e': 11, 'f': 13, 'g': 17, 'h': 19, 'i': 23, 'j': 29, 'k': 31,'l': 37, 'm': 41, 'n': 43,'o': 47, 'p': 53, 'q': 59, 'r': 61, 's': 67, 't': 71, 'u': 73, 'v': 79, 'w': 83, 'x': 89, 'y': 97,'z': 101}
    return 0 if not word else reduce(operator.mul, [letter_code[letter] for letter in word])

I have put more detailed analysis of these in my medium story.

Answer 4

This could be the simple function call

A mix of functional Code and Imperative style of code

static boolean isAnagram(String a, String b) {
    
    String sortedA = "";
    Object[] aArr = a.toLowerCase().chars().sorted().mapToObj(i -> (char) i).toArray();
    for (Object o: aArr) {
        sortedA = sortedA.concat(o.toString());
    }
    
    
    String sortedB = "";
    Object[] bArr = b.toLowerCase().chars().sorted().mapToObj(i -> (char) i).toArray();
    for (Object o: bArr) {
        sortedB = sortedB.concat(o.toString());
    }
    
    if(sortedA.equals(sortedB))    
        return true;
    else
        return false;    
}

Answer 5

let's take a question: Given two strings s and t, write a function to determine if t is an anagram of s.

For example, s = "anagram", t = "nagaram", return true. s = "rat", t = "car", return false.

Method 1(Using HashMap ):

public class Method1 {

    public static void main(String[] args) {
        String a = "protijayi";
        String b = "jayiproti";
        System.out.println(isAnagram(a, b ));// output => true

    }

    private static boolean isAnagram(String a, String b) {
        Map<Character ,Integer> map = new HashMap<>();
        for( char c : a.toCharArray()) {
            map.put(c,    map.getOrDefault(c, 0 ) + 1 );
        }
        for(char c : b.toCharArray()) {
            int count = map.getOrDefault(c, 0);
            if(count  == 0 ) {return false ; }
            else {map.put(c, count - 1 ) ; }
        }
        
        return true;
    }

}

Method 2 :

public class Method2 {
public static void main(String[] args) {
    String a = "protijayi";
    String b = "jayiproti";

    
    System.out.println(isAnagram(a, b));// output=> true
}

private static boolean isAnagram(String a, String b) {
   
    
    int[] alphabet = new int[26];
    for(int i = 0 ; i < a.length() ;i++) {
         alphabet[a.charAt(i) - 'a']++ ;
    }
    for (int i = 0; i < b.length(); i++) {
         alphabet[b.charAt(i) - 'a']-- ;
    }
    
    for(  int w :  alphabet ) {
         if(w != 0 ) {return false;}
    }
    return true;
    
}
}

Method 3 :

public class Method3 {
public static void main(String[] args) {
    String a = "protijayi";
    String b = "jayiproti";
    
    
    System.out.println(isAnagram(a, b ));// output => true
}

private static boolean isAnagram(String a, String b) {
    char[] ca = a.toCharArray() ;
    char[] cb = b.toCharArray();
    Arrays.sort(   ca     );
    
    Arrays.sort(   cb        );
    return Arrays.equals(ca , cb );
}
}

Method 4 :

public class AnagramsOrNot {
    public static void main(String[] args) {
        String a = "Protijayi";
        String b = "jayiProti";
        isAnagram(a, b);
    }

    private static void isAnagram(String a, String b) {
        Map<Integer, Integer> map = new LinkedHashMap<>();

        a.codePoints().forEach(code -> map.put(code, map.getOrDefault(code, 0) + 1));
        System.out.println(map);
        b.codePoints().forEach(code -> map.put(code, map.getOrDefault(code, 0) - 1));
        System.out.println(map);
        if (map.values().contains(0)) {
            System.out.println("Anagrams");
        } else {
            System.out.println("Not Anagrams");
        }
    }
}

In Python:

def areAnagram(a, b):
    if len(a) != len(b): return False
    count1 = [0] * 256
    count2 = [0] * 256
    for i in a:count1[ord(i)] += 1
    for i in b:count2[ord(i)] += 1

    for i in range(256):
        if(count1[i] != count2[i]):return False    

    return True


str1 = "Giniiii"
str2 = "Protijayi"
print(areAnagram(str1, str2))

Let's take another famous Interview Question: Group the Anagrams from a given String:

public class GroupAnagrams {
    public static void main(String[] args) {
        String a = "Gini Gina Protijayi iGin aGin jayiProti Soudipta";
        Map<String, List<String>> map = Arrays.stream(a.split(" ")).collect(Collectors.groupingBy(GroupAnagrams::sortedString));
        System.out.println("MAP => " + map);
        map.forEach((k,v) -> System.out.println(k +" and the anagrams are =>" + v ));
        /*
         Look at the Map output:
        MAP => {Giin=[Gini, iGin], Paiijorty=[Protijayi, jayiProti], Sadioptu=[Soudipta], Gain=[Gina, aGin]}
        As we can see, there are multiple Lists. Hence, we have to use a flatMap(List::stream)
        Now, Look at the output:
        Paiijorty and the anagrams are =>[Protijayi, jayiProti]
       
        Now, look at this output:
        Sadioptu and the anagrams are =>[Soudipta]
        List contains only word. No anagrams.
        That means we have to work with map.values(). List contains all the anagrams.
        
                     
        */
        String stringFromMapHavingListofLists = map.values().stream().flatMap(List::stream).collect(Collectors.joining(" "));
        System.out.println(stringFromMapHavingListofLists);
    }

    public static String sortedString(String a) {
        String sortedString = a.chars().sorted()
                .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString();

        return sortedString;

    }
    
    /*
     * The output : Gini iGin Protijayi jayiProti Soudipta Gina aGin
     * All the anagrams are side by side.
     */
}

Now to Group Anagrams in Python is again easy.We have to : Sort the lists. Then, Create a dictionary. Now dictionary will tell us where are those anagrams are( Indices of Dictionary). Then values of the dictionary is the actual indices of the anagrams.

def groupAnagrams(words):
 
    # sort each word in the list
    A = [''.join(sorted(word)) for word in words]
    dict = {}
    for indexofsamewords, names in enumerate(A):
     dict.setdefault(names, []).append(indexofsamewords)
    print(dict)
    #{'AOOPR': [0, 2, 5, 11, 13], 'ABTU': [1, 3, 4], 'Sorry': [6], 'adnopr': [7], 'Sadioptu': [8, 16], ' KPaaehiklry': [9], 'Taeggllnouy': [10], 'Leov': [12], 'Paiijorty': [14, 18], 'Paaaikpr': [15], 'Saaaabhmryz': [17], ' CNaachlortttu': [19], 'Saaaaborvz': [20]}
 
    for index in dict.values():
     print([words[i] for i in index])
 

if __name__ == '__main__':
 
    # list of words
    words = ["ROOPA","TABU","OOPAR","BUTA","BUAT" , "PAROO","Soudipta",
        "Kheyali Park", "Tollygaunge", "AROOP","Love","AOORP", "Protijayi","Paikpara","dipSouta","Shyambazaar",
        "jayiProti", "North Calcutta", "Sovabazaar"]
 
    groupAnagrams(words)
 

The Output :

['ROOPA', 'OOPAR', 'PAROO', 'AROOP', 'AOORP']
['TABU', 'BUTA', 'BUAT']
['Soudipta', 'dipSouta']
['Kheyali Park']
['Tollygaunge']
['Love']
['Protijayi', 'jayiProti']
['Paikpara']
['Shyambazaar']
['North Calcutta']
['Sovabazaar']

Another Important Anagram Question : Find the Anagram occuring Max. number of times. In the Example, ROOPA is the word which has occured maximum number of times. Hence, ['ROOPA' 'OOPAR' 'PAROO' 'AROOP' 'AOORP'] will be the final output.

from sqlite3 import collections
from statistics import mode, mean

import numpy as np


# list of words
words = ["ROOPA","TABU","OOPAR","BUTA","BUAT" , "PAROO","Soudipta",
        "Kheyali Park", "Tollygaunge", "AROOP","Love","AOORP",
         "Protijayi","Paikpara","dipSouta","Shyambazaar",
        "jayiProti", "North Calcutta", "Sovabazaar"]

print(".....Method 1....... ")

sortedwords = [''.join(sorted(word)) for word in words]
print(sortedwords)
print("...........")
LongestAnagram = np.array(words)[np.array(sortedwords) == mode(sortedwords)]
# Longest anagram 
print("Longest anagram by Method 1:")
print(LongestAnagram)

print(".....................................................")  

print(".....Method 2....... ")  

A = [''.join(sorted(word)) for word in words]

dict = {}

for indexofsamewords,samewords in  enumerate(A):
    dict.setdefault(samewords,[]).append(samewords)
#print(dict)  
#{'AOOPR': ['AOOPR', 'AOOPR', 'AOOPR', 'AOOPR', 'AOOPR'], 'ABTU': ['ABTU', 'ABTU', 'ABTU'], 'Sadioptu': ['Sadioptu', 'Sadioptu'], ' KPaaehiklry': [' KPaaehiklry'], 'Taeggllnouy': ['Taeggllnouy'], 'Leov': ['Leov'], 'Paiijorty': ['Paiijorty', 'Paiijorty'], 'Paaaikpr': ['Paaaikpr'], 'Saaaabhmryz': ['Saaaabhmryz'], ' CNaachlortttu': [' CNaachlortttu'], 'Saaaaborvz': ['Saaaaborvz']}
     
aa =  max(dict.items() , key = lambda x : len(x[1]))
print("aa => " , aa)    
word, anagrams = aa 
print("Longest anagram by Method 2:")
print(" ".join(anagrams))    

The Output :

.....Method 1....... 
['AOOPR', 'ABTU', 'AOOPR', 'ABTU', 'ABTU', 'AOOPR', 'Sadioptu', ' KPaaehiklry', 'Taeggllnouy', 'AOOPR', 'Leov', 'AOOPR', 'Paiijorty', 'Paaaikpr', 'Sadioptu', 'Saaaabhmryz', 'Paiijorty', ' CNaachlortttu', 'Saaaaborvz']
...........
Longest anagram by Method 1:
['ROOPA' 'OOPAR' 'PAROO' 'AROOP' 'AOORP']
.....................................................
.....Method 2....... 
aa =>  ('AOOPR', ['AOOPR', 'AOOPR', 'AOOPR', 'AOOPR', 'AOOPR'])
Longest anagram by Method 2:
AOOPR AOOPR AOOPR AOOPR AOOPR






















     

Answer 6

    String str1 = "evil";
    String str2 = "vile";

    int ana1 = 0;
    int ana2 = 0;

    for (int i = 0; i < str1.length(); i++) {
        ana1 += str1.charAt(i);
    }

    for (int i = 0; i < str1.length(); i++) {
        ana2 += str2.charAt(i);
    }

    if (ana1 == ana2) {
        System.out.println("Is anagram");
    }

Answer 7

Many complicated answers here. Base on the accepted answer and the comment mentioning the 'ac'-'bb' issue assuming A=65 B=66 C=67, we could simply use the square of each integer that represent a char and solve the problem:

public boolean anagram(String s, String t) {
    if(s.length() != t.length())
        return false;

    int value = 0;
    for(int i = 0; i < s.length(); i++){
        value += ((int)s.charAt(i))^2;
        value -= ((int)t.charAt(i))^2;
    }
    return value == 0;
}

Answer 8

// When this method returns 0 means strings are Anagram, else Not.

public static int isAnagram(String str1, String str2) {
        int value = 0;
        if (str1.length() == str2.length()) {
            for (int i = 0; i < str1.length(); i++) {
                value = value + str1.charAt(i);
                value = value - str2.charAt(i);
            }

        } else {
            value = -1;
        }
        return value;
    }

Answer 9

The simplest solution with complexity O(N) is using Map.

public static Boolean checkAnagram(String string1, String string2) {
    Boolean anagram = true;

    Map<Character, Integer> map1 = new HashMap<>();
    Map<Character, Integer> map2 = new HashMap<>();


    char[] chars1 = string1.toCharArray();
    char[] chars2 = string2.toCharArray();

    for(int i=0; i<chars1.length; i++) {
        if(map1.get(chars1[i]) == null) {
            map1.put(chars1[i], 1);
        } else {
            map1.put(chars1[i], map1.get(chars1[i])+1);
        }

        if(map2.get(chars2[i]) == null) {
            map2.put(chars2[i], 1);
        } else {
            map2.put(chars2[i], map2.get(chars2[i])+1);
        }
    }

    Set<Map.Entry<Character, Integer>> entrySet1 = map1.entrySet();
    Set<Map.Entry<Character, Integer>> entrySet2 = map2.entrySet();
    for(Map.Entry<Character, Integer> entry:entrySet1) {

        if(entry.getValue() != map2.get(entry.getKey())) {
            anagram = false;
            break;
        }
    }

    return anagram;
}

Answer 10

Two words are anagrams of each other if they contain the same number of characters and the same characters. You should only need to sort the characters in lexicographic order, and determine if all the characters in one string are equal to and in the same order as all of the characters in the other string.

Here's a code example. Look into Arrays in the API to understand what's going on here.

public boolean isAnagram(String firstWord, String secondWord) {
     char[] word1 = firstWord.replaceAll("[\\s]", "").toCharArray();
     char[] word2 = secondWord.replaceAll("[\\s]", "").toCharArray();
     Arrays.sort(word1);
     Arrays.sort(word2);
     return Arrays.equals(word1, word2);
}

Answer 11

Here is my solution.First explode the strings into char arrays then sort them and then comparing if they are equal or not. I guess time complexity of this code is O(a+b).if a=b we can say O(2A)

public boolean isAnagram(String s1, String s2) {

        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        if (s1.length() != s2.length())
            return false;

        char arr1[] = s1.toCharArray();
        char arr2[] = s2.toCharArray();
        Arrays.sort(arr1);
        Arrays.sort(arr2);



        for (char c : arr1) {
            sb1.append(c);
        }

        for (char c : arr2) {
            sb2.append(c);
        }

        System.out.println(sb1.toString());
        System.out.println(sb2.toString());

        if (sb1.toString().equals(sb2.toString()))
            return true;
        else
            return false;

    }

Answer 12

IMHO, the most efficient solution was provided by @Siguza, I have extended it to cover strings with space e.g: "William Shakespeare", "I am a weakish speller", "School master", "The classroom"

public int getAnagramScore(String word, String anagram) {

        if (word == null || anagram == null) {
            throw new NullPointerException("Both, word and anagram, must be non-null");
        }

        char[] wordArray = word.trim().toLowerCase().toCharArray();
        char[] anagramArray = anagram.trim().toLowerCase().toCharArray();

        int[] alphabetCountArray = new int[26];

        int reference = 'a';

        for (int i = 0; i < wordArray.length; i++) {
            if (!Character.isWhitespace(wordArray[i])) {
                alphabetCountArray[wordArray[i] - reference]++;
            }
        }
        for (int i = 0; i < anagramArray.length; i++) {
            if (!Character.isWhitespace(anagramArray[i])) {
                alphabetCountArray[anagramArray[i] - reference]--;
            }
        }

        for (int i = 0; i < 26; i++)
            if (alphabetCountArray[i] != 0)
                return 0;

        return word.length();

    }

Answer 13

private static boolean checkAnagram(String s1, String s2) {
   if (s1 == null || s2 == null) {
       return false;
   } else if (s1.length() != s2.length()) {
       return false;
   }
   char[] a1 = s1.toCharArray();
   char[] a2 = s2.toCharArray();
   int length = s2.length();
   int s1Count = 0;
   int s2Count = 0;
   for (int i = 0; i < length; i++) {
       s1Count+=a1[i];
       s2Count+=a2[i];
   }
   return s2Count == s1Count ? true : false;
}

Answer 14

I had written this program in java. I think this might also help:

public class Anagram {
    public static void main(String[] args) {
        checkAnagram("listen", "silent");
    }

    public static void checkAnagram(String str1, String str2) {
        boolean isAnagram = false;
        str1 = sortStr(str1);
        str2 = sortStr(str2);
        if (str1.equals(str2)) {
            isAnagram = true;
        }
        if (isAnagram) {
            System.out.println("Two strings are anagram");
        } else {
            System.out.println("Two string are not anagram");
        }

    }

    public static String sortStr(String str) {
        char[] strArr = str.toCharArray();
        for (int i = 0; i < str.length(); i++) {
            for (int j = i + 1; j < str.length(); j++) {
                if (strArr[i] > strArr[j]) {
                    char temp = strArr[i];
                    strArr[i] = strArr[j];
                    strArr[j] = temp;
                }
            }
        }
        String output = String.valueOf(strArr);
        return output;
    }
}

Answer 15

Here's a simple fast O(n) solution without using sorting or multiple loops or hash maps. We increment the count of each character in the first array and decrement the count of each character in the second array. If the resulting counts array is full of zeros, the strings are anagrams. Can be expanded to include other characters by increasing the size of the counts array.

class AnagramsFaster{

    private static boolean compare(String a, String b){
        char[] aArr = a.toLowerCase().toCharArray(), bArr = b.toLowerCase().toCharArray();
        if (aArr.length != bArr.length)
            return false;
        int[] counts = new int[26]; // An array to hold the number of occurrences of each character
        for (int i = 0; i < aArr.length; i++){
            counts[aArr[i]-97]++;  // Increment the count of the character at i
            counts[bArr[i]-97]--;  // Decrement the count of the character at i
        }
        // If the strings are anagrams, the counts array will be full of zeros
        for (int i = 0; i<26; i++)
            if (counts[i] != 0)
                return false;
        return true;
    }

    public static void main(String[] args){
        System.out.println(compare(args[0], args[1]));
    }
}

Answer 16

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
/**
 * Check if Anagram by Prime Number Logic
 * @author Pallav
 *
 */
public class Anagram {
    public static void main(String args[]) {
        System.out.println(isAnagram(args[0].toUpperCase(),
                args[1].toUpperCase()));
    }
/**
 * 
 * @param word : The String 1
 * @param anagram_word : The String 2 with which Anagram to be verified
 * @return true or false based on Anagram
 */
    public static Boolean isAnagram(String word, String anagram_word) {
        //If length is different return false
        if (word.length() != anagram_word.length()) {
            return false;
        }
        char[] words_char = word.toCharArray();//Get the Char Array of First String
        char[] anagram_word_char = anagram_word.toCharArray();//Get the Char Array of Second String
        int words_char_num = 1;//Initialize Multiplication Factor to 1
        int anagram_word_num = 1;//Initialize Multiplication Factor to 1 for String 2
        Map<Character, Integer> wordPrimeMap = wordPrimeMap();//Get the Prime numbers Mapped to each alphabets in English
        for (int i = 0; i < words_char.length; i++) {
            words_char_num *= wordPrimeMap.get(words_char[i]);//get Multiplication value for String 1
        }
        for (int i = 0; i < anagram_word_char.length; i++) {
            anagram_word_num *= wordPrimeMap.get(anagram_word_char[i]);//get Multiplication value for String 2
        }

        return anagram_word_num == words_char_num;
    }
/**
 * Get the Prime numbers Mapped to each alphabets in English
 * @return
 */
    public static Map<Character, Integer> wordPrimeMap() {
        List<Integer> primes = primes(26);
        int k = 65;
        Map<Character, Integer> map = new TreeMap<Character, Integer>();
        for (int i = 0; i < primes.size(); i++) {
            Character character = (char) k;
            map.put(character, primes.get(i));
            k++;
        }
        // System.out.println(map);
        return map;
    }
/**
 * get first N prime Numbers where Number is greater than 2
 * @param N : Number of Prime Numbers
 * @return
 */
    public static List<Integer> primes(Integer N) {
        List<Integer> primes = new ArrayList<Integer>();
        primes.add(2);
        primes.add(3);

        int n = 5;
        int k = 0;
        do {
            boolean is_prime = true;
            for (int i = 2; i <= Math.sqrt(n); i++) {
                if (n % i == 0) {
                    is_prime = false;
                    break;
                }
            }

            if (is_prime == true) {
                primes.add(n);

            }
            n++;
            // System.out.println(k);
        } while (primes.size() < N);

        // }

        return primes;
    }

}

Answer 17

Thanks for pointing out to make comment, while making comment I found that there was incorrect logic. I corrected the logic and added comment for each piece of code.

// Time complexity: O(N) where N is number of character in String
// Required space :constant space.
// will work for string that contains ASCII chars

private static boolean isAnagram(String s1, String s2) {

    // if length of both string's are not equal then they are not anagram of each other 
    if(s1.length() != s2.length())return false;

    // array to store the presence of a character with number of occurrences.   
    int []seen = new int[256];

    // initialize the array with zero. Do not need to initialize specifically  since by default element will initialized by 0.
    // Added this is just increase the readability of the code. 
    Arrays.fill(seen, 0);

    // convert each string to lower case if you want to make ABC and aBC as anagram, other wise no need to change the case.  
    s1 = s1.toLowerCase();
    s2 = s2.toLowerCase();

    //  iterate through the first string and count the occurrences of each character
    for(int i =0; i < s1.length(); i++){
        seen[s1.charAt(i)] = seen[s1.charAt(i)] +1;
    }

    // iterate through second string and if any char has 0 occurrence then return false, it mean some char in s2 is there that is not present in s1.
    // other wise reduce the occurrences by one every time .
    for(int i =0; i < s2.length(); i++){
        if(seen[s2.charAt(i)] ==0)return false;
        seen[s2.charAt(i)] = seen[s2.charAt(i)]-1;
    }

    // now if both string have same occurrence of each character then the seen array must contains all element as zero. if any one has non zero element return false mean there are 
    // some character that either does not appear in one of the string or/and mismatch in occurrences 
    for(int i = 0; i < 256; i++){
        if(seen[i] != 0)return false;
    }
    return true;
}

Answer 18

How a mathematician might think about the problem before writing any code:

1. The relation "are anagrams" between strings is an equivalence relation, so partitions the set of all strings into equivalence classes.
2. Suppose we had a rule to choose a representative (crib) from each class, then it's easy to test whether two classes are the same by comparing their representatives.
3. An obvious representative for a set of strings is "the smallest element by lexicographic order", which is easy to compute from any element by sorting. For example, the representative of the anagram class containing 'hat' is 'aht'.

In your example "schoolmaster" and "theclassroom" are anagrams because they are both in the anagram class with crib "acehlmoorsst".

In pseudocode:

>>> def crib(word):
...     return sorted(word)
...
>>> crib("schoolmaster") == crib("theclassroom")
True

Answer 19

If you sort either array, the solution becomes O(n log n). but if you use a hashmap, it's O(n). tested and working.

char[] word1 = "test".toCharArray();
char[] word2 = "tes".toCharArray();

Map<Character, Integer> lettersInWord1 = new HashMap<Character, Integer>();

for (char c : word1) {
    int count = 1;
    if (lettersInWord1.containsKey(c)) {
        count = lettersInWord1.get(c) + 1;
    }
    lettersInWord1.put(c, count);
}

for (char c : word2) {
    int count = -1;
    if (lettersInWord1.containsKey(c)) {
        count = lettersInWord1.get(c) - 1;
    }
    lettersInWord1.put(c, count);
}

for (char c : lettersInWord1.keySet()) {
    if (lettersInWord1.get(c) != 0) {
        return false;
    }
}

return true;

Answer 20

So far all proposed solutions work with separate char items, not code points. I'd like to propose two solutions to properly handle surrogate pairs as well (those are characters from U+10000 to U+10FFFF, composed of two char items).

1) One-line O(n logn) solution which utilizes Java 8 CharSequence.codePoints() stream:

static boolean areAnagrams(CharSequence a, CharSequence b) {
    return Arrays.equals(a.codePoints().sorted().toArray(),
                         b.codePoints().sorted().toArray());
}

2) Less elegant O(n) solution (in fact, it will be faster only for long strings with low chances to be anagrams):

static boolean areAnagrams(CharSequence a, CharSequence b) {
    int len = a.length();
    if (len != b.length())
        return false;

    // collect codepoint occurrences in "a"
    Map<Integer, Integer> ocr = new HashMap<>(64);
    a.codePoints().forEach(c -> ocr.merge(c, 1, Integer::sum));

    // for each codepoint in "b", look for matching occurrence
    for (int i = 0, c = 0; i < len; i += Character.charCount(c)) {
        int cc = ocr.getOrDefault((c = Character.codePointAt(b, i)), 0);
        if (cc == 0)                        
            return false;            
        ocr.put(c, cc - 1);
    }
    return true;
}

Answer 21

Works perfectly! But not a good approach because it runs in O(n^2)

boolean isAnagram(String A, String B) {
    if(A.length() != B.length())
        return false;

   A = A.toLowerCase();
   B = B.toLowerCase();

   for(int i = 0; i < A.length(); i++){
       boolean found = false;
       for(int j = 0; j < B.length(); j++){
           if(A.charAt(i) == B.charAt(j)){
               found = true;
               break;
           }
       }
       if(!found){
           return false;
       }
   }

   for(int i = 0; i < B.length(); i++){
       boolean found = false;
       for(int j = 0; j < A.length(); j++){
           if(A.charAt(j) == B.charAt(i)){
               found = true;
               break;
           }
       }
       if(!found){
           return false;
       }
   }

   int sum1 = 0, sum2 = 0;
   for(int i = 0; i < A.length(); i++){
       sum1 += (int)A.charAt(i);
       sum2 += (int)B.charAt(i);               
   }

   if(sum1 == sum2){
       return true;
   } 
   return false;
}

Answer 22

Here is another approach using HashMap in Java

public static boolean isAnagram(String first, String second) {
    if (first == null || second == null) {
        return false;
    }
    if (first.length() != second.length()) {
        return false;
    }
    return doCheckAnagramUsingHashMap(first.toLowerCase(), second.toLowerCase());
}

private static boolean doCheckAnagramUsingHashMap(final String first, final String second) {
    Map<Character, Integer> counter = populateMap(first, second);
    return validateMap(counter);
}

private static boolean validateMap(Map<Character, Integer> counter) {
    for (int val : counter.values()) {
        if (val != 0) {
            return false;
        }
    }
    return true;
}

Here is the test case

@Test
public void anagramTest() {
    assertTrue(StringUtil.isAnagram("keep" , "PeeK"));
    assertFalse(StringUtil.isAnagram("Hello", "hell"));
    assertTrue(StringUtil.isAnagram("SiLeNt caT", "LisTen cat"));       
}

Answer 23

A way to solve this - based on Sai Kiran's answer..

import java.util.Scanner;

public class Anagram {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter first word : ");
        String word1 = sc.nextLine();
        System.out.print("Enter second word : ");
        String word2 = sc.nextLine();

        sc.close();

        System.out.println("Is Anagram : " + isAnagram(word1, word2));
    }

    private static boolean isAnagram(String word1, String word2) {

        if (word1.length() != word2.length()) {
            System.err.println("Words length didn't match!");
            return false;
        }

        char ch1, ch2;
        int len = word1.length(), sumOfWord1Chars = 0, sumOfWord2Chars = 0;

        for (int i = 0; i < len; i++) {
            ch1 = word1.charAt(i);
            if (word2.indexOf(ch1) < 0) {
                System.err.println("'" + ch1 + "' not found in \"" + word2
                        + "\"");
                return false;
            }
            sumOfWord1Chars += word1.charAt(i);

            ch2 = word2.charAt(i);
            if (word1.indexOf(ch2) < 0) {
                System.err.println("'" + ch2 + "' not found in \"" + word1
                        + "\"");
                return false;
            }
            sumOfWord2Chars += word2.charAt(i);
        }

        if (sumOfWord1Chars != sumOfWord2Chars) {
            System.err
                    .println("Sum of both words didn't match, i.e., words having same characters but with different counts!");
            return false;
        }

        return true;
    }
}

Answer 24

I know this is an old question. However, I'm hoping this can be of help to someone. The time complexity of this solution is O(n^2).

public boolean areAnagrams(final String word1, final String word2) {
        if (word1.length() != word2.length())
            return false;

        if (word1.equals(word2))
            return true;

        if (word1.length() == 0 && word2.length() == 0)
            return true;

        String secondWord = word2;
        for (int i = 0; i < word1.length(); i++) {
            if (secondWord.indexOf(word1.charAt(i)) == -1)
                return false;

            secondWord = secondWord.replaceFirst(word1.charAt(i) + "", "");
        }

        if (secondWord.length() > 0)
            return false;

        return true;
}

Answer 25

I saw that no one has used the "hashcode" approach to find out the anagrams. I found my approach little different than the approaches discussed above hence thought of sharing it. I wrote the below code to find the anagrams which works in O(n).

/**
 * This class performs the logic of finding anagrams
 * @author ripudam
 *
 */
public class AnagramTest {

    public static boolean isAnagram(final String word1, final String word2) {

            if (word1 == null || word2 == null || word1.length() != word2.length()) {
                 return false;
            }

            if (word1.equals(word2)) {
                return true;
            }

            final AnagramWrapper word1Obj = new AnagramWrapper(word1);
            final AnagramWrapper word2Obj = new AnagramWrapper(word2);

            if (word1Obj.equals(word2Obj)) {
                return true;
            }

            return false;
        }

        /*
         * Inner class to wrap the string received for anagram check to find the
         * hash
         */
        static class AnagramWrapper {
            String word;

            public AnagramWrapper(final String word) {
                this.word = word;
            }

            @Override
            public boolean equals(final Object obj) {

                return hashCode() == obj.hashCode();
            }

            @Override
            public int hashCode() {
                final char[] array = word.toCharArray();
                int hashcode = 0;
                for (final char c : array) {
                    hashcode = hashcode + (c * c);
                }
                return hashcode;
            }
         }
    }

Answer 26

Sorry, the solution is in C#, but I think the different elements used to arrive at the solution is quite intuitive. Slight tweak required for hyphenated words but for normal words it should work fine.

    internal bool isAnagram(string input1,string input2)
    {
        Dictionary<char, int> outChars = AddToDict(input2.ToLower().Replace(" ", ""));
        input1 = input1.ToLower().Replace(" ","");
        foreach(char c in input1)
        {
            if (outChars.ContainsKey(c))
            {
                if (outChars[c] > 1)
                    outChars[c] -= 1;
                else
                    outChars.Remove(c);
            }
        }
        return outChars.Count == 0;
    }

    private Dictionary<char, int> AddToDict(string input)
    {
        Dictionary<char, int> inputChars = new Dictionary<char, int>();
        foreach(char c in input)
        {
            if(inputChars.ContainsKey(c))
            {
                inputChars[c] += 1;
            }
            else
            {
                inputChars.Add(c, 1);
            }     
        }
        return inputChars;
    }

Answer 27

A simple method to figure out whether the testString is an anagram of the baseString.

private static boolean isAnagram(String baseString, String testString){
    //Assume that there are no empty spaces in either string.

    if(baseString.length() != testString.length()){
        System.out.println("The 2 given words cannot be anagram since their lengths are different");
        return false;
    }
    else{
        if(baseString.length() == testString.length()){
            if(baseString.equalsIgnoreCase(testString)){
                System.out.println("The 2 given words are anagram since they are identical.");
                return true;
            }
            else{
                List<Character> list = new ArrayList<>();

                for(Character ch : baseString.toLowerCase().toCharArray()){
                    list.add(ch);
                }
                System.out.println("List is : "+ list);

                for(Character ch : testString.toLowerCase().toCharArray()){
                    if(list.contains(ch)){
                        list.remove(ch);
                    }
                }

                if(list.isEmpty()){
                    System.out.println("The 2 words are anagrams");
                    return true;
                }
            }
        }
    }
    return false;
}

Answer 28

A similar answer may have been posted in C++, here it is again in Java. Note that the most elegant way would be to use a Trie to store the characters in sorted order, however, that's a more complex solution. One way is to use a hashset to store all the words we are comparing and then compare them one by one. To compare them, make an array of characters with the index representing the ANCII value of the characters (using a normalizer since ie. ANCII value of 'a' is 97) and the value representing the occurrence count of that character. This will run in O(n) time and use O(m*z) space where m is the size of the currentWord and z the size for the storedWord, both for which we create a Char[].

public static boolean makeAnagram(String currentWord, String storedWord){
    if(currentWord.length() != storedWord.length()) return false;//words must be same length
    Integer[] currentWordChars = new Integer[totalAlphabets];
    Integer[] storedWordChars = new Integer[totalAlphabets];
    //create a temp Arrays to compare the words
    storeWordCharacterInArray(currentWordChars, currentWord);
    storeWordCharacterInArray(storedWordChars, storedWord);
    for(int i = 0; i < totalAlphabets; i++){
        //compare the new word to the current charList to see if anagram is possible
        if(currentWordChars[i] != storedWordChars[i]) return false;
    }
    return true;//and store this word in the HashSet of word in the Heap
}
//for each word store its characters
public static void storeWordCharacterInArray(Integer[] characterList, String word){
    char[] charCheck = word.toCharArray();
    for(char c: charCheck){
        Character cc = c;
        int index = cc.charValue()-indexNormalizer;
        characterList[index] += 1;
    }
}

Answer 29

I am a C++ developer and the code below is in C++. I believe the fastest and easiest way to go about it would be the following:

Create a vector of ints of size 26, with all slots initialized to 0, and place each character of the string into the appropriate position in the vector. Remember, the vector is in alphabetical order and so if the first letter in the string is z, it would go in myvector[26]. Note: This can be done using ASCII characters so essentially your code will look something like this:

string s = zadg;
for(int i =0; i < s.size(); ++i){
    myvector[s[i] - 'a'] = myvector['s[i] - 'a'] + 1;
} 

So inserting all the elements would take O(n) time as you would only traverse the list once. You can now do the exact same thing for the second string and that too would take O(n) time. You can then compare the two vectors by checking to see if the counters in each slot are the same. If they are, that means you had the same number of EACH character in both the strings and thus they are anagrams. The comparing of the two vectors should also take O(n) time as you are only traversing through it once.

Note: The code only works for a single word of characters. If you have spaces, and numbers and symbols, you can just create a vector of size 96 (ASCII characters 32-127) and instead of saying - 'a' you would say - ' ' as the space character is the first one in the ASCII list of characters.

I hope that helps. If i have made a mistake somewhere, please leave a comment.

Answer 30

O(n) solution without any kind of sorting and using only one map.

public boolean isAnagram(String leftString, String rightString) {
  if (leftString == null || rightString == null) {
    return false;
  } else if (leftString.length() != rightString.length()) {
    return false;
  }

  Map<Character, Integer> occurrencesMap = new HashMap<>();

  for(int i = 0; i < leftString.length(); i++){
    char charFromLeft = leftString.charAt(i);
    int nrOfCharsInLeft = occurrencesMap.containsKey(charFromLeft) ? occurrencesMap.get(charFromLeft) : 0;
    occurrencesMap.put(charFromLeft, ++nrOfCharsInLeft);
    char charFromRight = rightString.charAt(i);
    int nrOfCharsInRight = occurrencesMap.containsKey(charFromRight) ? occurrencesMap.get(charFromRight) : 0;
    occurrencesMap.put(charFromRight, --nrOfCharsInRight);
  }

  for(int occurrencesNr : occurrencesMap.values()){
    if(occurrencesNr != 0){
      return false;
    }
  }

  return true;
}

and less generic solution but a little bit faster one. You have to place your alphabet here:

public boolean isAnagram(String leftString, String rightString) {
  if (leftString == null || rightString == null) {
    return false;
  } else if (leftString.length() != rightString.length()) {
    return false;
  }

  char letters[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
  Map<Character, Integer> occurrencesMap = new HashMap<>();
  for (char l : letters) {
    occurrencesMap.put(l, 0);
  }

  for(int i = 0; i < leftString.length(); i++){
    char charFromLeft = leftString.charAt(i);
    Integer nrOfCharsInLeft = occurrencesMap.get(charFromLeft);
    occurrencesMap.put(charFromLeft, ++nrOfCharsInLeft);
    char charFromRight = rightString.charAt(i);
    Integer nrOfCharsInRight = occurrencesMap.get(charFromRight);
    occurrencesMap.put(charFromRight, --nrOfCharsInRight);
  }

  for(Integer occurrencesNr : occurrencesMap.values()){
    if(occurrencesNr != 0){
      return false;
    }
  }

  return true;
}