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

Answer 1

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.

Answer 2

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

Answer 3

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.