Anagram algorithm in java

Question

I would like to make anagram algorithm but This code doesn't work. Where is my fault ? For example des and sed is anagram but output is not anagram Meanwhile I have to use string method. not array. :)

public static boolean isAnagram(String s1 , String s2)
{
    String delStr="";
    String newStr="";

    for(int i=0;i<s1.length();i++)
    {
        for(int j=0 ; j < s2.length() ; j++)
        {
            if(s1.charAt(i)==s2.charAt(j))
            {
                delStr=s1.substring(i,i+1);
                newStr=s2.replace(delStr,"");
            }
        }           
    }

    if(newStr.equals(""))
        return true;
    else
        return false;
}

Tyrothricin

Can you explain what you are seeing wrong? Does an exception throw? Does it just not return what you expect? Does it infinite-loop? – Intercolumniation

Can you give an example as to what is an Anagram in your case? – Arched

No, only I wrote des and sed but output is not anagram – Tyrothricin

Why does your code not work? Because you overwrite newStr with s2 (less a letter) every time you get a match. For example, if s2 is ab, when you match b, newStr becomes a, then when you match a, newStr does not become the empty string, but becomes b (since it is s2 less the matching character). It is not the only bug in your code (repeated characters, different length strings), but it is the one that you are going to see first. – Nonscheduled

Probably worth noting after all this time that Java has progressed sufficiently to make this a one-liner: Arrays.equals( a.chars().filter(Character::isAlphabetic).sorted().toArray(), b.chars().filter(Character::isAlphabetic).sorted().toArray()); – Hopper

Answer 1

An easier way might be to just sort the chars in both strings, and compare whether they are equal:

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

        // Early termination check, if strings are of unequal lengths,
        // then they cannot be anagrams
        if ( s1.length() != s2.length() ) {
            return false;
        }
        s1=s1.toLowerCase();
        s2=s2.toLowerCase();
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        Arrays.sort(c1);
        Arrays.sort(c2);
        String sc1 = new String(c1);
        String sc2 = new String(c2);
        return sc1.equals(sc2);
}

Personally I think it's more readable than nested for-loops =p

This has O(n log n) run-time complexity, where n is the length of the longer string.

Edit: this is not the optimal solution. See @aam1r's answer for the most efficient approach (i.e. what you should actually say in an interview)

Jar

lol. +1 You can use Arrays.equals() to compare the sorted arrays. – Arrest

@PeterLawrey: Or use a simple loop, which is equivalent. But not this – Shakhty

@user1873885 Unfortunately "isn't working" does not give me any information that I can use to help you with =( – Jar

@Jar I don't understand problem. I write des and sed but input is not anagram. Meanwhile I dont use array class. Only string methods – Tyrothricin

@user1873885 you need to show us the full code, particularly 1) where you are using isAnagram, 2) what is expected input / output and 3) what you are actually getting – Jar

@user1873885 - Assuming you have fixed the braces on the if, your code is not working because, after each loop iteration, newStr is set to the result of deleting only the last match from s2. – Oospore

@sampson-chen: I would assume abuse by user while using this function and add this check: code if (s1 == null || s2 == null) { return false; } code Else it will throw NPE when either of s1 or s2 is null. – Perfunctory

Dear all future readers, this is by far one of the least performant answers. Do not use – Shakhty

@Shakhty - yup, aam1r's answer is the optimal solution, vote that one up instead. – Jar

@Jar could you please explain where does logn comes from? – Pritchard

@ÖmerFarukAlmalı O(n log n) is from comparison-based sorting: en.wikipedia.org/wiki/Comparison_sort – Jar

So the space complexity is O(n) due to the additional char arrays? – Centner

It's a little bit simpler to use Arrays.equals here rather than converting back to strings. docs.oracle.com/javase/8/docs/api/java/util/… – Johannejohannes

Answer 2

This can be done in linear time using constant space. Here is pseudo-code to help you get started:

// Create new hashtable/hashmap to keep track of how many times each character
// is being used
character_map -> new hash map

// Initial check. If lengths are not the same, they can't be anagrams.
if s1.length != s2.length:
    throw exception "Not anagrams"

// Add all characters from s1 to hashmap. Increment the value to keep track of
// number of occurences
foreach character c1 in s1:
    character_map[c1]++

// Iterate through all character in s2 and decrement count of each character.
foreach character c2 in s2:
    character_map[c2]--

// If they are anagrams, each character should be at "0" count at the point.
// If we come across a character that is not, it means that they are not anagrams
foreach key k, value v in character_map:
    if v != 0:
            throw exception "Not anagrams"

This code does not sort and hence can be done using simple loops. The overall runtime is O(n) and overall space is O(1) -- hence being the fastest solution. The number of elements you can have in the hash map is constant (i.e. you know how many items there are in your alphabet set).

Astir

Ahh bucket sort, my hero. +1. By the way, this is O(1) space, not O(n) – Shakhty

If lengths are not the same, they can't be anagrams. -> First remove the whitespaces. – Wrath

Answer 3

if(s1.charAt(i)==s2.charAt(j))
        delStr=s1.substring(i,i+1);
        newStr=s2.replace(delStr,"");

This code is a nice demonstration of why you should always have curly braces around your if, even if there is only a single statement. Your 2nd assignment is actually outside the if-condition, and will always happen.

The best way to check for two strings to be Anagram is to convert them to a character array (String#toCharArray). Then sort them using Arrays.sort method. And do the comparison on them.

---

Updated : -

If you just want to use String methods, then you don't actually need a nested loop there. You can do it with just one.

Here's the modified code of yours: -

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

    if (s1.length() != s2.length()) {
        return false;
    }

    for(int i = 0; i < s2.length(); i++) {

            if( !s1.contains("" + s2.charAt(i))) {
                return false;
            }

            s1 = s1.replaceFirst("" + s2.charAt(i), "");
            s2 = s2.replaceFirst("" + s2.charAt(i), "");
    }
    return true;
}

Arched

Yeah, i agree. It is always recommended to have curly braces around an if. – Noella

@user1873885. May be. But to get it to work, you need to tell what is an Anagram? I can't understand the logic of the code. – Arched

@Shakhty yepp, the code still doesnt work, thats why its not accepted yet :P, upvotes are for pointing the blunder in the code . – Unguarded

@durron597.. Ah! Actually, this was the only logical error that I could notice in the code, because I don't know what Anagram OP is talking about. – Arched

@GanGnaMStYleOverFlowErroR: There are now three correct answers in this thread, all of which have fewer upvotes than this answer. Rohit, you should give yourself the disciplined badge now ;) – Shakhty

@durron597.. Lol.. Do you really want me to have that? :( I have updated my answer, not with some code though, as OP has already got 3 of them. – Arched

@Shakhty haha, yeah, (upvotes!=accepted). and i did upvote all the 3 answers(including yours) :), however i think Rohits answer is quite useful:) – Unguarded

@durron597. There you go. I added a code, for it to be a valid answer. ;) – Arched

@RohitJain: What, you don't want a Disciplined badge? :) Also, that code doesn't work, consider the strings "abbbccc" and "aaaaabc" – Shakhty

@durron597.. No :( I have always had an image of in-disciplined guy. I don't want to loose that image. – Arched

@durron597.. Let me modify it. – Arched

Answer 4

What would be more efficient is to compare the Strings in sorted order.

public static boolean isAnagram(String s1 , String s2) {
    return s1.length() == s2.length() 
        && checkSum(s1) == checkSum(s2)
        && Arrays.equals(lettersSorted(s1), lettersSorted(s2));
}

static long checkSum(String s) {
    long sqrSum = 0;
    for(int i = 0; i < s.length(); s++) {
       char ch = s.charAt(i);
       sqrSum += ch + (1L << ch);
    }
}

static char[] lettersSorted(String s) {
    char[] chars = s.toCharArray();
    Arrays.sort(chars);
    return chars;
}

This is an O(N ln N) algorithm, but will be O(N) on an average if the Strings are typically not anagrams.

Arrest

Haha, that's 3 of us so far - adage about great minds and all, eh? ;) – Jar

@Jar So I added something different. ;) – Arrest

@PeterLawrey lol that would be faster, too bad I already upvoted you ;) – Shakhty

what is the purpose of checkSum method here? – Buchanan

@lining the purpose of the checkSum is to perform an O(n) check which typically will detect which strings don't match. – Arrest

In addition to checking the sum, you could also check the XOR in the same loop. The combination of sum and XOR should make "collisions" considerably rarer. – Johannejohannes

Answer 5

I'm not sure what you're trying to do, but I'm pretty sure it won't work (and it runs in O(n^2). Try this (which runs in O(n log n)) instead:

public static boolean isAnagram(String s1, String s2){
  if (s1.length() != s2.length()) return false;

  char[] c1 = s1.toCharArray();
  char[] c2 = s2.toCharArray();

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

  for(int i = 0; i < c1.length; i++) {
    if(c1[i] != c2[i]) return false;
  }

  return true;
}

Shakhty

+1 If you are going to check the length, I would do it before calling toCharArray. – Arrest

The for loop here can be replaced with return Arrays.equals(c1, c2);. docs.oracle.com/javase/8/docs/api/java/util/… – Johannejohannes

Answer 6

There is a various possible solution of determining if a string is Anagram or not. 1. using Array.sort() predefined method

String string1 = "abc";
String string2 = "bca";
char[] chars = string1.toCharArray();
char[] chars2 = string2.toCharArray();
Arrays.sort(chars);
Arrays.sort(chars2);
string1 = new String(chars);
string2 = new String(chars2);
if (string1.equalsIgnoreCase(string2)) {
  System.out.println("Anagram");
} else {
  System.out.println("Not Anagram");
}

Time complexity: Ω(n log n) 2. By Iterative method

char [] charArray = str.toCharArray();
if(str.length() == str1.length()){
    for(char ch : charArray){
        if(str1.indexOf(ch) == -1){
            System.out.println("Not Anagram");
        } 
    }    
    System.out.println("Anagram");
} else {
    System.out.println("Not Anagram");
}

Time complexity: Ω(n)

Though, the first algorithm is more readable second algorithm really executes faster.

Tampon

If you want to test for anagrams in a case-insensitive way, you should convert both strings to lowercase (or uppercase) before sorting. Otherwise {'Z', 'a'} and {'A', 'z'} are both in sorted order and the strings won't be equal ignoring case. The second "iterative" algorithm isn't correct for the strings "aab" and "abb". – Johannejohannes

you can also add a break statement inside of index check if statement to make it more efficient – Copious

Answer 7

The reason it doesn't work:

Using "des" and "sed" as an example.

In the last iteration for which it matches, it will evaluate:

if(s1.charAt(i)==s2.charAt(j))
{
    delStr=s1.substring(i,i+1);
    newStr=s2.replace(delStr,"");
}

Which will be: if( "s" == "s" )

It will then enter the if block, and evaluate

newStr = "sed".replace("s","");

which will give you "ed", instead of an empty string.

The moral of the story is that you are always replacing characters from s2 less one character, which will never be empty.

Using String.replace() is bad anyway, because it will replace all instances of the character by default. With String.replace(), it would consider "sed" to be an anagram of "seeeeeeed". You would do better to use String.replaceFirst().

In any case, a starting point is to make the following modifications:

String newStr = s2;
...
// inside if block
newStr = newStr.replaceFirst( delStr, "" );

Tramway

Answer 8

Below is a concise code snippet that determines whether two strings are anagrams in a single iteration of both strings, plus a final iteration of a 256 element array. This approach avoids sorting the characters in the strings and converting to/from Strings/char arrays by recording character counts in a mapping array.

static boolean isAnagram(String s1, String s2) {
    if (s1.length() != s2.length()) return false;
    int n = s1.length();
    int[] charMap = new int[256];
    for (int i = 0; i < n; i++) {
        char c1 = s1.charAt(i);
        charMap[c1]++;
        char c2 = s2.charAt(i);
        charMap[c2]--;
    }
    for (int i = 0; i < charMap.length; i++) {
        if (charMap[i] != 0) return false;
    }
    return true;
}

This code basically increments and decrements an index location in an array corresponding to a character. If any of the array elements are non-zero at the end of the iteration, there were an unequal amount of increments and decrements, and therefore the strings contain differing characters and cannot be anagrams of each other.

Given that this algorithm iterates the two same sized strings once, runtime is O(n). Space complexity is O(1) as the charMap is always constant depending on charset requirements.

Mowbray

Answer 9

import java.util.Scanner;

public class Anagrams {

static boolean isAnagram(String a, String b) {
    a = a.toLowerCase();
    b = b.toLowerCase();
    if (a.length() != b.length()) {
        return false;
    }

    char[] chars = a.toCharArray();
    for (char c : chars) {
        int index = b.indexOf(c);
        if (index != -1) {
            b = b.substring(0, index) + b.substring(index + 1, b.length());
        } else {
            return false;
        }
    }
    return b.isEmpty();
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    String a = scan.next();
    String b = scan.next();
    scan.close();
    boolean ret = isAnagram(a, b);
    System.out.println((ret) ? "Anagrams" : "Not Anagrams");

    }
}

Betelgeuse

Answer 10

public boolean checkAnagram(String s, String t) {
    s = s.toLowerCase();
    t = t.toLowerCase();

    // We can ignore blanks
    char[] word1 = s.replaceAll("\\s","").toCharArray();
    char[] word2 = t.replaceAll("\\s","").toCharArray();

    // Anagrams length should be the same
    if (word1.length != word2.length) {
        return false;
    }

    // Sorting arrays is pretty fast, it can be O(logn) 
    Arrays.sort(word1);
    Arrays.sort(word2);

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

    return false;
}

Ingeringersoll

Answer 11

Using HashMap
public boolean isAnagram(String word, String anagram) {
    if (word.length() != anagram.length())
        return false;

    int count = 0;
    Map<Character, Integer> map = new HashMap<>();

    for (int i = 0; i < word.length(); i++) {
        if (!map.containsKey(word.charAt(i)))
            map.put(word.charAt(i), 1);
        else
            map.put(word.charAt(i), map.get(word.charAt(i)) + 1);
    }

    for (int i = 0; i < anagram.length(); i++) {
        if (!map.containsKey(anagram.charAt(i)))
            return false;
        else if (map.get(anagram.charAt(i)) >= 1)
            map.put(anagram.charAt(i), map.get(anagram.charAt(i)) - 1);
        else
            return false;
    }

    return true;
}

Kodak

Answer 12

just making sure, you are trying to check to see if s1 is a anagram of s2 correct? That would also mean s2 is a an anagram of s1. So i would just sort s1 and s2 and check to see if they are equal.

String string1 = "fdafdas";
String string2 = "fdwqkjl";
char[] chars = string1.toCharArray();
char[] chars2 = string2.toCharArray();
Arrays.sort(chars);
Arrays.sort(chars2);
string1 = new String(chars);
string2 = new String(chars2);
if (string1.equals(string2)) {
    //They are an anagram
}

Lenticel

opps, didnt know so many people were posting the same thing. My bad. – Lenticel

Answer 13

public boolean isAnagram(String a, String b) {

  boolean result = false;

  final String one = a.replaceAll("[\\s+\\W+]", "").toLowerCase();

  final String two = b.replaceAll("[\\s+\\W+]", "").toLowerCase();

  if (one.length() == two.length()) {

      final char[] oneArray =  one.toCharArray();

      final char[] twoArray =  two.toCharArray(); 

      Arrays.sort(oneArray);

      Arrays.sort(twoArray);

      result = Arrays.equals(oneArray, twoArray);

    }

  return result; 

}

Semiology

This is elegant but has complexity of sorting algorithm. – Lucillelucina

Answer 14

I guess the following solution has O(n) complexity, let me know if someone differs.

import java.util.HashMap;
import java.util.Scanner;


public class Anagrams {

    static boolean isAnagram(String word1, String word2)
    {
        if(word1.length() != word2.length()) {
            return false;
        }
        int flag=0;
        HashMap<Character,Integer> table = new HashMap<Character,Integer>();
        for(int i=0; i< word1.length();i++) {
            table.put(word1.charAt(i),1);
        }

        for(int i=0; i< word2.length();i++) {
            if(table.containsKey(word2.charAt(i))) {
                continue;
            } else {
                flag=1;
                break;
            }   
        }
        return flag == 0;
    }

    public static void main(String[] args) {
        System.out.println("Enter your string");
        Scanner sc= new Scanner(System.in);
        String word1= sc.nextLine();
        String word2=sc.nextLine();

         boolean result = isAnagram(word1,word2);
         if(result) {
             System.out.println("The words are Anagrams");
         } else{
             System.out.println("The words are not Anagrams");   
         }
    }
}

Perfectible

Calling a map 'table' :(. Using continue and break when not necessary. Eh. – Lucillelucina

@Lucillelucina I would like you to modify and post if you want to make it better. "table" is just a random name, I am not using this code in some real-life product. Was just practicing. – Perfectible

Yeah. Continue and break still remains though. – Lucillelucina

@SahilMadan I did a basic refactor of your code. I think that you can do the rest. – Chartulary

Answer 15

O(n) solution without any kind of sorting and using only one map. Also added proper null check missing in other solutions.

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:

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;
}

Lucillelucina

Answer 16

Here's a Simpler approach relying mostly on java The complete code is here https://github.com/rdsr/algorithms/blob/master/src/jvm/misc/AnagramsList.java (Note this solves a related by different problem)

class Anagram {
    Map<Character, Integer> anagram;

    Anagram(String s) {
        anagram = new HashMap<Character, Integer>();

        for (final Character c : s.toCharArray()) {
            if (anagram.containsKey(c)) {
                anagram.put(c, 1 + anagram.get(c));
            } else {
                anagram.put(c, 1);
            }
        }
    }

    @Override
    public int hashCode() {
        //.. elided
    }

    @Override
    public boolean equals(Object obj) {
        //.. elided
    }
}


    public class Anagrams {
            public static void main(String[] args) {
                System.out.println(new Anagram("abc").equals(new Anagram("bac")));
            }
        }

Eulaeulachon

One suggestion. you can get anagram.get(c) and check null instead of containsKey ( you are iterating two times just to check ) – Vladivostok

Answer 17

Faster version using bit vector approach for anagram substrings

public boolean isAnagram(String _source1, String _source2)
{

    int flag = 0, char_index = 0, counter = 0;
    if(_source2.length() < _source1.length()){
        return false;
    }
    char[] _stringchar = _source1.toCharArray();
    char[] _tocheck = _source2.toCharArray();
    for(char character : _stringchar)
    {
        char_index = character - 'a';
        if((flag & (1 << char_index)) == 0)
            flag |= (1 << char_index);
    }

    for(char toCheckcChar : _tocheck)
    {
        char_index = toCheckcChar - 'a';

        if((flag & (1 << char_index)) > 0)
            counter++;
        else
            counter = 0;

        if(counter == _source1.length())
            return true;

    }

    return false;
}

Lithium

Answer 18

The simple reason is, because replace function creates a new String object. It does not do anything to the actual string (in your case s2), because in Java, strings are final by nature. So as pointed out by cmonkey, you are always removing one character from your string s2, but in reality a new String object is created with 1 character less, s2 remains as is.

The simple way to get this working in your case would be to create a new string object and assign it to yourself.

{
    s2=s2.replace(delString,"");
    ....
    if(s2.empty()) return true;
    return false;
}

Octopus

Answer 19

just see at line newStr=s2.replace(delStr,"");

what you are doing here replacing a char in s2 and assigning back to newStr, means you are not changing anything in s2. Just replace this code by below one it will work fine

newStr=newStr.replace(delStr,"");

Billionaire

Answer 20

I took some time out to actually pen down the logic and write a code to check for two strings, if they are anagrams or not. Of course with the help of the above answers! XD

public static void main(String[] args) {

    Map<Character, Integer> char_map = new HashMap<Character, Integer>();
    Map<Character, Integer> empty_map = new HashMap<Character, Integer>();
    String a = "HelloP";
    String b = "HePlol";

    if (a.length() != b.length()) {
        System.out.println("false");
        System.exit(0);
    }

    for (char c : a.toLowerCase().toCharArray()) {
        empty_map.put(c, 0);
        if (char_map.containsKey(c))
            char_map.put(c, 1 + char_map.get(c));
        else
            char_map.put(c, 1);
    }

    for (char c : b.toLowerCase().toCharArray())
        if (char_map.containsKey(c))
            char_map.put(c, char_map.get(c) - 1);

    System.out.println(char_map.equals(empty_map));
}

Ser

(I don't quite like the name empty_map.) You can use old = char_map.put(c, 1); if (null != old) char_map.put(c, old + 1) for one lookup less per character. – Circumambulate

Answer 21

I think this works with complexity O(2n)

public static boolean isAnagram(String str1, String str2){
    if(str1.length() != str2.length()){ return false;}
    int[] buffer = new int[256];
    for(char ch : str1.toCharArray()){
        buffer[ch]++;
    }
    for(char ch : str2.toCharArray()){
        if(buffer[ch]==0) return false;
        buffer[ch] = (buffer[ch] > 0)?(buffer[ch] - 1 ): -1 ;   
    }
    return true;
}

Precondition

Answer 22

This is a Java implementation that I wrote for using an array instead of a HashMap. This saves space, plus arrays are really fast.

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

        int[] arr = new int[123];
        for (char c : s.toCharArray())
            arr[c]++;
        for (char c : t.toCharArray())
            arr[c]--;
        for (int i : arr)
            if (i != 0)
                return false;
        return true;
    }

Sim

Answer 23

import java.util.Scanner;

public class JavaProgram
{
    public static void main(String[] input)
    {
        String str1, str2;
        int len, len1, len2, i, j, found=0, not_found=0;
        Scanner scan = new Scanner(System.in);

        System.out.print("Enter First String : ");
        str1 = scan.nextLine();
        System.out.print("Enter Second String : ");
        str2 = scan.nextLine();

        len1 = str1.length();
        len2 = str2.length();

        if(len1 == len2)
        {
            len = len1;
            for(i=0; i<len; i++)
            {
                found = 0;
                for(j=0; j<len; j++)
                {
                    if(str1.charAt(i) == str2.charAt(j))
                    {
                        found = 1;
                        break;
                    }
                }
                if(found == 0)
                {
                    not_found = 1;
                    break;
                }
            }
            if(not_found == 1)
            {
                System.out.print("Strings are not Anagram to Each Other..!!");
            }
            else
            {
                System.out.print("Strings are Anagram");
            }
        }
        else
        {
            System.out.print("Both Strings Must have the same number of Character to be an Anagram");
        }
    }
}

Ledesma

You should test your code before posting it as an answer. – Gabi

Answer 24

public class Anagram {
    public boolean isAnagram(
            String left, 
            String right) {
        if (left.length() == right.length()) {
            Map<Character, Integer> map = new HashMap<>();
            char[] a = left.toCharArray(), b = right.toCharArray();
            for (int i = 0; i < a.length; i++) {
                accumulate(map, a[i]);
                accumulate(map, b[i]);
            }
            for (char c : map.keySet()) {
                if (map.get(c) > 0) {
                    return false;
                }
            }
            return true;
        } else {
            return false;
        }
    }

    private void accumulate(
            Map<Character, Integer> map, 
            char key) {
        if (map.containsKey(key)) {
            map.put(key, Math.abs(map.get(key) - 1));
        } else {
            map.put(key, 1);
        }
    }
}

Coronal

Answer 25

Here is my solution from your aspect

private static boolean isAnagram(String s1, String s2){
    int count = 0;
    boolean flag = false;

    if(s1.length() != s2.length()){
        return false;
    }
    //checks whether both word's letters are the same
    for (int i = 0; i < s1.length(); i++){
        for (int j = 0; j < s2.length(); j++){
            if(s1.charAt(i) == s2.charAt(j)){
                count++;
                break;
            }
        }
    }
    //if count equals to one of the Strings length then it is an anagram
    if(count == s2.length() ){
        flag = true;
    }
    return flag;
}

Equality

Answer 26

    String str1="Mother In Law";
    String str2="Hitler Woman";
    char[] anag1=str1.replaceAll("\\s", "").toLowerCase().toCharArray();
    char[] anag2=str2.replaceAll("\\s", "").toLowerCase().toCharArray();
    Arrays.sort(anag1);
    Arrays.sort(anag2);
    System.out.println(Arrays.equals(anag1, anag2)? "words are anagrams":"words are not anagrams");

Backbone

Answer 27

public static boolean isAnagram(String s1, String s2) {
    boolean aux = true;
    if (s1.length() != s2.length()){
        aux = false;
    }else{ 
        for (int i = 0; i < s1.length(); i++)
            if(s2.toUpperCase().indexOf(s1.toUpperCase().substring(i, i+1)) == -1) aux = false;
    }
    return aux;
}

Foredoom

Answer 28

public class SampleAnagram {

    public static void main(String ...s) {


        String s1 = "work";
        String s2="kwro";

        System.out.println(s1.charAt(0));

        int s1L = s1.length();
        int s2L = s2.length();

        int totalCount = 0;

            for(int i=0;i<s1L;i++) {

                for(int j=0;j<s2L;j++) {

                if(s1.charAt(i)==(s2.charAt(j))) {

                    totalCount = totalCount+1;
                }
            }
        }

            System.out.println(totalCount);


            if(s1.length()==totalCount && s2.length()==totalCount) {

                System.out.println("given the input as anagram");
            }

    }



}

Zeidman

Answer 29

Here is another suggestion without initialising an int[256] but an int[26] for English alphabet.

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

static boolean isAnagram(String s1, String s2) {
    if (s1.length() != s2.length()) {
        return false;
    }
    int[] countArray = new int[26];
    for (int i = 0; i < s1.length(); i++) {
        countArray[getIndex(i, s1)]++;
        countArray[getIndex(i, s2)]--;
    }
    for (int i = 0; i < countArray.length; i++) {
        if (countArray[i] != 0) {
            return false;
        }
    }
    return true;
}

public static int getIndex(int position, String value) {
    return value.charAt(position) - 'a';
}

Best George Tsopouridis

Newmann

Answer 30

public static boolean isAnagram(String s1, String s2) {
    if (s1.length() != s2.length()) {
        return false;
    }
    Map<Character, Integer> frequencies = new HashMap<>();
    for (int i = 0; i < s1.length(); i++) {
        if (frequencies.containsKey(s1.charAt(i))) {
            frequencies.put(s1.charAt(i), frequencies.get(s1.charAt(i)) + 1);
        } else {
            frequencies.put(s1.charAt(i), 1);
        }
    }
    for (int i = 0; i < s2.length(); i++) {
        if (frequencies.containsKey(s2.charAt(i))) {
            int frequency = frequencies.get(s2.charAt(i));
            if (--frequency == 0) {
                frequencies.remove(s2.charAt(i));
            } else {
                frequencies.put(s2.charAt(i), frequencies.get(s2.charAt(i)) - 1);
            }
        }
    }
    return frequencies.isEmpty();
}

Embryotomy

this algorithm has time complexity of O(N) and space complexity of O(N) – Embryotomy

Answer 31

1. Compare lengths of both strings if equal
2. Convert both strings to lowercase so you can compare efficiently
3. Loop to check if String1 contains a character in String2.

4. Set a counter to the length of one of the strings and decrease -1 when there's a match

   public boolean isAnagram(String s1, String s2) {
   
   if(s1.length() != s2.length()) {
       return false;
   }
   
   int counter= s1.length();
   s1 = s1.toLowerCase();
   s2= s2.toLowerCase();
   
   for (int i=0; i<s1.length();i++ ) {
   
           if (s2.contains(s1.charAt(i)+"")) {
   
               counter--;              
       }
   }
   
   if (counter<=0) {
   
       return true;
   }
   return false;
   }
   

Goff

Answer 32

Using the Java streams this can be simplified in just 5 lines of code (https://github.com/vspiliop/java-puzzles/blob/master/src/gy/etiolo/puzzles/streams/Anagrams.java):

/**
 * Are two strings anagrams.
 */
public class Anagrams {
  public static void main(String ... args) {
    String word1 = "abcdefg";
    String word2 = "gfedabc";

    System.out.println("Are they anagrams: " + isAnagram(word1, word2));
  }

  private static boolean isAnagram(String word1, String word2) {
    int [] mask = new int[26];
    Arrays.fill(mask, 0);
    word1.toLowerCase().chars().forEach(c -> mask['z' - c]++);
    word2.toLowerCase().chars().forEach(c -> mask['z' - c]--);
    return Arrays.stream(mask).sum() == 0;
  }
}

Check ascii table here: http://www.asciitable.com/

Plumley

Answer 33

A solution, optimized for performance.

What does differently to other solutions:

• Only in the absolute worst case it iterates once through text1 and once through text2
• Fails fast: returns false as soon as it encounters a character in text1 that is not part of text2
• Stores histogram as int[], which is much faster than HashMaps or similar
• Can process strings with any character (even emojis 😉)

Example Code:

public static boolean check(String text1, String text2) {
    requireNonNull(text1, "text1 must not be null");
    requireNonNull(text2, "text2 must not be null");
    if (text1 == text2) return true;

    var text1Chars = text1.toCharArray();
    var text2Chars = text2.toCharArray();
    if (text1Chars.length != text2Chars.length) return false;

    var text2Counts = new int[Character.MAX_CODE_POINT];
    var text2Index = 0;

    loopThroughText1:
    for (char charOfText1 : text1Chars) {
        if (text2Counts[charOfText1] > 0) {
            text2Counts[charOfText1]--;
        } else {
            while (text2Index < text2Chars.length) {
                var charOfText2 = text2Chars[text2Index++];
                if (charOfText1 == charOfText2) {
                    continue loopThroughText1;
                }
                text2Counts[charOfText2]++;
            }
            return false;
        }
    }
    return text2Index >= text2Chars.length;
}

The corresponding test method:

@ParameterizedTest
@CsvSource({
        "a,a,true",
        "a,b,false",
        "aa,a,false",
        "a,aa,false",
        "aa,aa,true",
        "vhjsd682ahjsvdi7861rUZVFD/Ias6srf871r23,vhjsd682ahjsvdi7861rUZVFD/Ias6srf871r23,true",
        "A,a,false",
        "🎈,🎈,true",
        "🎈,💣,false",
})
public void check(String text1, String text2, boolean expected) {
    assertEquals(AnagramChecker.check(text1, text2), expected);
}

Rorry

Answer 34

I'm adding this as a unique O(n) approach, although, much like a hash comparison, it really only determines whether it's highly probable that two strings are anagrams of each other rather than providing complete certainty.

public static boolean isAnagram(String s1, String s2) {
    if (s1.length()!=s2.length()) return false;
    int sum1=0, sum2=0;
    int xor1=0, xor2=0;
    int prod1=1, prod2=1;
    for (int i=0; i<s1.length(); i++) {
        char c1=s1.charAt(i);
        char c2=s2.charAt(i);
        sum1 += c1;
        sum2 += c2;
        xor1 ^= c1;
        xor2 ^= c2;
        prod1 *= c1;
        prod2 *= c2;
    }
    return sum1==sum2 && xor1==xor2 && prod1==prod2;
}

Cheder

Answer 35

I think here's more readable and easy way to solve this problem. Complexity is O(n) and two maps only

public static boolean isAnagram(String word, String word2) {

if (word.equals(word2)) return true;
if (word == null || word2 == null) return false;
if (word.length() != word2.length()) return false;

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

for (int i = 0; i < word.length(); i++) {
    map.merge(word.charAt(i), 1, (oldVal, value) -> oldVal++);
}

for (int i = 0; i < word2.length(); i++) {
    map2.merge(word2.charAt(i), 1, (oldVal, value) -> oldVal++);
}

return map.equals(map2);

}

Elijaheliminate

Answer 36

public static boolean isAnagram(String str1, String str2){
    if(str1.length() != str2.length())
      return false;
    int lengthStr1 = str1.length();
    for(char c : str2.toCharArray()) {
       str1 = str1.replaceFirst(c+"", "");
    if(str1.length() == lengthStr1--)
       return false;
    }
    return true;
}

Bowline

Seems to work, but it runs in O(n^2) since no sorting happens. Also, please indent your code. – Aubarta

Answer 37

You can use a combination of Streams and maths as in:

public static boolean isAnagram(String s1, String s2){
    if ( s1.length() != s2.length() ) {
        return false;
    }
    int s1Sum = s1.chars().sum();
    int s2Sum = s2.chars().sum();
    return s1Sum == s2Sum;
}

Penates

Answer 38

import java.util.*;
class Anagrams 
{
    public static void main(String[] args) 
    {
        System.out.println("Enter the two words");
        Scanner scan = new Scanner(System.in);
        String word1 = scan.next();
        String word2=scan.next();

        StringBuilder sb1= new StringBuilder(word1);
        StringBuilder sb2= new StringBuilder(word2);
        int count=0;
        System.out.println("length ! "+sb1.length());
        System.out.println("Length ! "+sb2.length());
        if(sb1.length()==sb2.length()){
            for(int i=0;i<sb1.length();i++){
                for(int k=0;k<sb2.length();k++){
                    if(sb1.charAt(i)==sb2.charAt(k)){
                        sb2.deleteCharAt(k);
                        count++;
                        System.out.println("Count is "+count);
                        break;
                    }
                }
            }

            if(count==sb1.length()){

                System.out.println("Anagrams!");
            }
            else{
                System.out.println("Not Anagrams");
            }
        }
        else{
            System.out.println("Not equal in length");
        }
    }
}

Nicolasanicolau

Maybe some more explanation? – Sievers