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 lt Character gt  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 lt phrase1Arr length  i                                for int j   0  j  lt  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 lt Character gt  convertStringToArraylist String str          ArrayList lt Character gt  charList   new ArrayList lt Character gt            for int i   0  i lt str length   i               charList add str charAt i                  return charList

User · Answer

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 lt Character  Integer gt  occurrencesMap   new HashMap lt  gt        for int i   0  i  lt  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 lt Character  Integer gt  occurrencesMap   new HashMap lt  gt       for  char l   letters        occurrencesMap put l  0          for int i   0  i  lt  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

User · Answer

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  lt  str length    i                  for  int j   i   1  j  lt  str length    j                      if  strArr i   gt  strArr j                         char temp   strArr i                       strArr i    strArr j                       strArr j    temp                                                    String output   String valueOf strArr           return output

User · Answer

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 lt char  int gt  outChars   AddToDict input2 ToLower   Replace                    input1   input1 ToLower   Replace                  foreach char c in input1                        if  outChars ContainsKey c                                 if  outChars c   gt  1                      outChars c  -  1                  else                     outChars Remove c                                   return outChars Count    0             private Dictionary lt char  int gt  AddToDict string input                Dictionary lt char  int gt  inputChars   new Dictionary lt char  int gt             foreach char c in input                        if inputChars ContainsKey c                                 inputChars c     1                            else                               inputChars Add c  1                                        return inputChars

User · Answer

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  lt  s length    i             value      int s charAt i   2          value -    int t charAt i   2            return value    0

User · Answer

By using more memory  an HashMap of at most N 2 elements we do not need to sort the strings   public static boolean areAnagrams String one  String two        if  one length      two length              String s0   one toLowerCase            String s1   two toLowerCase            HashMap lt Character  Integer gt  chars   new HashMap lt Character  Integer gt  one length             Integer count          for  char c   s0 toCharArray                  count   chars get c               count   Integer valueOf count    null   count   1   1               chars put c  count                     for  char c   s1 toCharArray                  count   chars get c               if  count    null                    return false                else                   count--                  chars put c  count                                   for  Integer i   chars values                  if  i    0                    return false                                  return true        else           return false            This function is actually running in O N      instead of O NlogN  for the solution that sorts the strings  If I were to assume that you are going to use only alphabetic characters I could only use an array of  26 ints  from a to z without accents or decorations  instead of the hashmap   If we define that   N    one     two  we do one iteration over N  once over one to increment the counters  and once to decrement them over two   Then to check the totals we iterate over at mose N 2   The other algorithms described have one advantage  they do not use extra memory assuming that Arrays sort uses inplace versions of QuickSort or merge sort  But since we are talking about anagrams I will assume that we are talking about human languages  thus words should not be long enough to give memory issues

User · Answer

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

User · Answer

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  lt  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

User · Answer

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 lt Integer  Integer gt  ocr   new HashMap lt  gt  64       a codePoints   forEach c - gt  ocr merge c  1  Integer  sum            for each codepoint in  b   look for matching occurrence     for  int i   0  c   0  i  lt  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

User · Answer

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  lt  str1 length    i                      value   value   str1 charAt i                   value   value - str2 charAt i                            else               value   -1                    return value

User · Answer

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  lt  wordArray length  i                  if   Character isWhitespace wordArray i                      alphabetCountArray wordArray i  - reference                                     for  int i   0  i  lt  anagramArray length  i                  if   Character isWhitespace anagramArray i                      alphabetCountArray anagramArray i  - reference --                                   for  int i   0  i  lt  26  i                if  alphabetCountArray i     0                  return 0           return word length

User · Answer

How a mathematician might think about the problem before writing any code    The relation  are anagrams  between strings is an equivalence relation  so partitions the set of all strings into equivalence classes  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  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     gt  gt  gt  def crib word           return sorted word       gt  gt  gt  crib  schoolmaster      crib  theclassroom   True

User · Answer

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  lt  length  i             s1Count  a1 i          s2Count  a2 i           return s2Count    s1Count   true   false

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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    quot anagram quot   t    quot nagaram quot   return true  s    quot rat quot   t    quot car quot   return false  Method 1 Using HashMap    public class Method1        public static void main String   args            String a    quot protijayi quot           String b    quot jayiproti quot           System out println isAnagram a  b       output   gt  true             private static boolean isAnagram String a  String b            Map lt Character  Integer gt  map   new HashMap lt  gt             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    quot protijayi quot       String b    quot jayiproti quot             System out println isAnagram a  b      output  gt  true    private static boolean isAnagram String a  String b                 int   alphabet   new int 26       for int i   0   i  lt  a length    i               alphabet a charAt i  -  a                 for  int i   0  i  lt  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    quot protijayi quot       String b    quot jayiproti quot                 System out println isAnagram a  b       output   gt  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    quot Protijayi quot           String b    quot jayiProti quot           isAnagram a  b              private static void isAnagram String a  String b            Map lt Integer  Integer gt  map   new LinkedHashMap lt  gt              a codePoints   forEach code - gt  map put code  map getOrDefault code  0    1            System out println map           b codePoints   forEach code - gt  map put code  map getOrDefault code  0  - 1            System out println map           if  map values   contains 0                 System out println  quot Anagrams quot              else               System out println  quot Not Anagrams quot                       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    quot Giniiii quot  str2    quot Protijayi quot  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    quot Gini Gina Protijayi iGin aGin jayiProti Soudipta quot           Map lt String  List lt String gt  gt  map   Arrays stream a split  quot   quot    collect Collectors groupingBy GroupAnagrams  sortedString            System out println  quot MAP   gt   quot    map           map forEach  k v  - gt  System out println k   quot  and the anagrams are   gt  quot    v                         Look at the Map output          MAP   gt   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   gt  Protijayi  jayiProti                  Now  look at this output          Sadioptu and the anagrams are   gt  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  quot   quot             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     quot ROOPA quot   quot TABU quot   quot OOPAR quot   quot BUTA quot   quot BUAT quot     quot PAROO quot   quot Soudipta quot            quot Kheyali Park quot    quot Tollygaunge quot    quot AROOP quot   quot Love quot   quot AOORP quot    quot Protijayi quot   quot Paikpara quot   quot dipSouta quot   quot Shyambazaar quot            quot jayiProti quot    quot North Calcutta quot    quot Sovabazaar quot         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     quot ROOPA quot   quot TABU quot   quot OOPAR quot   quot BUTA quot   quot BUAT quot     quot PAROO quot   quot Soudipta quot            quot Kheyali Park quot    quot Tollygaunge quot    quot AROOP quot   quot Love quot   quot AOORP quot             quot Protijayi quot   quot Paikpara quot   quot dipSouta quot   quot Shyambazaar quot            quot jayiProti quot    quot North Calcutta quot    quot Sovabazaar quot    print  quot      Method 1         quot    sortedwords       join sorted word   for word in words  print sortedwords  print  quot             quot   LongestAnagram   np array words  np array sortedwords     mode sortedwords     Longest anagram  print  quot Longest anagram by Method 1  quot   print LongestAnagram   print  quot                                                       quot      print  quot      Method 2         quot      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  quot aa   gt   quot    aa      word  anagrams   aa  print  quot Longest anagram by Method 2  quot   print  quot   quot  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   gt     AOOPR     AOOPR    AOOPR    AOOPR    AOOPR    AOOPR    Longest anagram by Method 2  AOOPR AOOPR AOOPR AOOPR AOOPR

User · Answer

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  lt  A length    i            boolean found   false         for int j   0  j  lt  B length    j                if A charAt i     B charAt j                   found   true                 break                               if  found              return false                    for int i   0  i  lt  B length    i            boolean found   false         for int j   0  j  lt  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  lt  A length    i            sum1     int A charAt i          sum2     int B charAt i                           if sum1    sum2          return true           return false

User · Answer

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  lt  len  i                  ch1   word1 charAt i               if  word2 indexOf ch1   lt  0                    System err println       ch1      not found in       word2                                                  return false                            sumOfWord1Chars    word1 charAt i                ch2   word2 charAt i               if  word1 indexOf ch2   lt  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

User · Answer

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

User · Answer

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 lt Character gt  list   new ArrayList lt  gt                      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

User · Answer

To change this template  choose Tools   Templates    and open the template in the editor       package Algorithms   import java util ArrayList  import java util Arrays  import java util HashMap  import javax swing JOptionPane              author Mokhtar     public class Anagrams          Write aprogram to check if two words are anagrams     public static void main String   args            Anagrams an new Anagrams            ArrayList lt String gt  l new ArrayList lt String gt             String result JOptionPane showInputDialog  How many words to test anagrams            if Integer parseInt result   gt 1                            for int i 0 i lt Integer parseInt result  i                                   String word JOptionPane showInputDialog  Enter word    i                   l add word                                System out println an isanagrams l                      else                       JOptionPane showMessageDialog null   Can not be tested   nYou can test two words or more                          private static String sortString  String w                 char   ch   w toCharArray            Arrays sort ch           return new String ch              public boolean isanagrams ArrayList lt String gt  l                boolean isanagrams true           ArrayList lt String gt  anagrams   null          HashMap lt String  ArrayList lt String gt  gt  map    new HashMap lt String  ArrayList lt String gt  gt             for int i 0 i lt l size   i                          String word   l get i           String sortedWord   sortString word               anagrams   map get  sortedWord            if  anagrams    null   anagrams   new ArrayList lt String gt             anagrams add word           map put sortedWord  anagrams                              for int h 0 h lt l size   h                                  if  anagrams contains l get h                                          isanagrams false                      break                                               return isanagrams

User · Answer

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  lt  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

User · Answer

Seems to be very awkward for such a simple task    Firstly    Your loops are much too complicated  Try something like this    public static String lettersOnly String word         int length   word length        StringBuilder end   new StringBuilder length       char x       for  int i    length - 1   i  gt   0  i--            x   word charAt i           if  Character isLetter x                 end append x                       return end toString      This is a much more simplistic way of checking if they are anagrams   You could also create a separate method for all of the printing which would be much easier   And lastly  just use       String ltrsOnlyOne   lettersOnly wordOne       String ltrsOnlyTwo   lettersOnly wordTwo     for creating the strings

User · Answer

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  lt  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 lt 26  i                if  counts i     0                  return false          return true             public static void main String   args           System out println compare args 0   args 1

User · Answer

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  amp  amp  word2 length      0              return true           String secondWord   word2          for  int i   0  i  lt  word1 length    i                  if  secondWord indexOf word1 charAt i      -1                  return false               secondWord   secondWord replaceFirst word1 charAt i                                if  secondWord length    gt  0              return false           return true

User · Answer

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 lt Character  Integer gt  counter   populateMap first  second       return validateMap counter      private static boolean validateMap Map lt Character  Integer gt  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

User · Answer

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  lt  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  lt  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  lt  256  i             if seen i     0 return false            return true

User · Answer

String str1    evil       String str2    vile        int ana1   0      int ana2   0       for  int i   0  i  lt  str1 length    i              ana1    str1 charAt i              for  int i   0  i  lt  str1 length    i              ana2    str2 charAt i              if  ana1    ana2            System out println  Is anagram

User · Answer

You should use something like that       for  int i               isFound   false          for  int j                   if                                             isFound   true                            Default value for isFound should be false  Just it

User · Answer

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

User · Answer

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 lt Character  Integer gt  lettersInWord1   new HashMap lt Character  Integer gt      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

User · Answer

The simplest solution with complexity O N  is using Map   public static Boolean checkAnagram String string1  String string2        Boolean anagram   true       Map lt Character  Integer gt  map1   new HashMap lt  gt         Map lt Character  Integer gt  map2   new HashMap lt  gt           char   chars1   string1 toCharArray        char   chars2   string2 toCharArray         for int i 0  i lt 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 lt Map Entry lt Character  Integer gt  gt  entrySet1   map1 entrySet        Set lt Map Entry lt Character  Integer gt  gt  entrySet2   map2 entrySet        for Map Entry lt Character  Integer gt  entry entrySet1             if entry getValue      map2 get entry getKey                   anagram   false              break                       return anagram

User · Answer

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 lt Character  Integer gt  wordPrimeMap   wordPrimeMap     Get the Prime numbers Mapped to each alphabets in English         for  int i   0  i  lt  words char length  i                  words char num    wordPrimeMap get words char i     get Multiplication value for String 1                   for  int i   0  i  lt  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 lt Character  Integer gt  wordPrimeMap             List lt Integer gt  primes   primes 26           int k   65          Map lt Character  Integer gt  map   new TreeMap lt Character  Integer gt             for  int i   0  i  lt  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 lt Integer gt  primes Integer N            List lt Integer gt  primes   new ArrayList lt Integer gt             primes add 2           primes add 3            int n   5          int k   0          do               boolean is prime   true              for  int i   2  i  lt   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    lt  N                          return primes

User · Answer

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    quot  quot       Object   aArr   a toLowerCase   chars   sorted   mapToObj i - gt   char  i  toArray        for  Object o  aArr            sortedA   sortedA concat o toString                         String sortedB    quot  quot       Object   bArr   b toLowerCase   chars   sorted   mapToObj i - gt   char  i  toArray        for  Object o  bArr            sortedB   sortedB concat o toString                    if sortedA equals sortedB               return true      else         return false

User · Answer

Some other solution without sorting   public static boolean isAnagram String s1  String s2         case insensitive anagram      StringBuffer sb   new StringBuffer s2 toLowerCase         for  char c  s1 toLowerCase   toCharArray             if  Character isLetter c                 int index   sb indexOf String valueOf c                if  index    -1                     char does not exist in other s2                 return false                            sb deleteCharAt index                       for  char c  sb toString   toCharArray               only allow whitespace as left overs         if   Character isWhitespace c                return false                      return true

User · Answer

We re walking two equal length strings and tracking the differences between them  We don t care what the differences are  we just want to know if they have the same characters or not  We can do this in O n 2  without any post processing  or a lot of primes    public class TestAnagram     public static boolean isAnagram String first  String second        String positive   first toLowerCase        String negative   second toLowerCase         if  positive length      negative length            return false             int   counts   new int 26        int diff   0       for  int i   0  i  lt  positive length    i            int pos    int  positive charAt i  - 97     convert the char into an array index       if  counts pos   gt   0       the other string doesn t have this         diff       an increase in differences         else      it does have it         diff--     a decrease in differences               counts pos        track it        int neg    int  negative charAt i  - 97        if  counts neg   lt   0       the other string doesn t have this         diff       an increase in differences         else      it does have it         diff--     a decrease in differences               counts neg --     track it            return diff    0         public static void main String   args        System out println isAnagram  zMarry    zArmry        true     System out println isAnagram  basiparachromatin    marsipobranchiata        true     System out println isAnagram  hydroxydeoxycorticosterones    hydroxydesoxycorticosterone        true     System out println isAnagram  hydroxydeoxycorticosterones    hydroxydesoxycorticosterons        false     System out println isAnagram  zArmcy    zArmry        false         Yes this code is dependent on the ASCII English character set of lowercase characters but it shouldn t be hard to modify to other languages  You can always use a Map Character  Int  to track the same information  it ll just be slower

[java] How to check if two words are anagrams

Examples related to java

Examples related to string

Examples related to algorithm

Examples related to anagram