Finding anagram using hashmap

Question

Here is my java solution to determine if t is an anagram of s(return true or false). It failed when comes to really large strings(for example, output: false, expected: true).

what's the problem in my codes?

import java.util.HashMap;
import java.util.Map;

public class solution {
    public static void main(String[] args){
    String s = "anfefeg";    // true
    String t = "fegafen";
    System.out.println(isAnagram(s,t));
    }
    public static boolean isAnagram(String s, String t) {
        defaultHashMap<Character, Integer> countS = new defaultHashMap<>(0);
        defaultHashMap<Character, Integer> countT = new defaultHashMap<>(0);
        if (s.length() != t.length()){
            return false;
        }
        // count frequencies of characters 
        for (int i=0; i < s.length(); i++){
            countS.put(s.charAt(i), countS.get(s.charAt(i)) + 1);
            countT.put(t.charAt(i), countT.get(t.charAt(i)) + 1);
        }
//        System.out.println(countS.entrySet());
//        System.out.println(countT.entrySet());

        // compare to map
        for (Map.Entry<Character, Integer> entry : countT.entrySet()){
            if (entry.getValue() != countS.get(entry.getKey())){
                return false;
            }
        }
        return true;
    }
}
/*
define a defaultHashMap class extending hashmap
*/
class defaultHashMap <K,V> extends HashMap<K,V> {
    protected V defaultValue;
    public defaultHashMap(V defaultValue) {
        this.defaultValue = defaultValue;
    }
    @Override
    public V get(Object k) {
        return containsKey(k) ? super.get(k) : defaultValue;
    }

}

https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ — shmosel, Dec 14 '17 at 20:48
[This example works.](https://ideone.com/2nieoW) Please provide an example that actually demonstrates the problem. — shmosel, Dec 14 '17 at 20:50
@shmosel, two strings of length 50018 caused the code to fail. They are too large to post here. If you don't mind, you can run it on leetcode.https://leetcode.com/problems/valid-anagram/description/ — Hongli Bu, Dec 14 '17 at 21:03
Why define a custom `defaultHashMap` when you can just call `getOrDefault()`? — shmosel, Dec 14 '17 at 21:04
@shmosel. Thank you for letting me know that. I didn't know it before. I can try it! — Hongli Bu, Dec 14 '17 at 21:06
FYI, Java convention is to begin class names with uppercase. — shmosel, Dec 14 '17 at 21:07

score 4 · Accepted Answer · answered Dec 14 '17 at 21:20

I'd say it's because you're comparing Integer instances with != instead of equals. Java usually caches small values of Integer, so if you convert a small number like 5 to an Integer multiple times, it usually returns the exact same object, which is probably why your program works for small strings.

But when you start creating large Integers, like your program will do for really long strings, then Java will just create a new Integer each time so even though the values are the same, the objects are different and == and != won't work, and you have to use equals instead.

This should fix your problem. Change

        if (entry.getValue() != countS.get(entry.getKey())) {
            return false;
        }

to

        if (! entry.getValue().equals(countS.get(entry.getKey()))) {
            return false;
        }

It works!!! Thank you so much! I learned a lot here, and it's really important to a java beginner! — Hongli Bu, Dec 14 '17 at 21:26

score 1 · Answer 2 · answered Jul 15 '19 at 01:29

Another approach through ArrayList:

public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    System.out.println("Enter 1st string");
    String string1 = sc.nextLine().toLowerCase();

    System.out.println("Enter 2nd string");
    String string2 = sc.nextLine().toLowerCase();

    ArrayList<Character> arr1 = new ArrayList<>();
    ArrayList<Character> arr2 = new ArrayList<>();

    //Adding chars of a string to ArrayList
    for (Character c : string1.toCharArray()) {
        arr1.add(c);
    }

    //Adding chars from a string to ArrayList
    for (Character c : string2.toCharArray()) {
        arr2.add(c);
    }

    Collections.sort(arr1);
    Collections.sort(arr2);

    if (arr1.equals(arr2)) {
        System.out.println("BOTH STRINGS ARE ANAGRAM");
    } else
        System.out.println("STRINGS ARE NOT ANAGRAM !!");

    sc.close();
}

score 0 · Answer 3 · answered Feb 23 '20 at 02:40

We can use map to do in efficient way and time complexity is O(n)

package com.test;

import java.util.HashMap;

public class Anagram {
    public static void main(String ar[]) {
        String str="anagram";
        String str1="anagram";
        char ch[]=str.toCharArray();
        char ch1[]=str1.toCharArray();
        HashMap<?, ?> map=constructMap(ch);
        HashMap<?, ?> mapq=constructMap(ch1);
        if(map.equals(mapq)) {
            System.out.println("Both are Anagram");
        }else {
            System.out.println("Not");
        }
    }

    private static HashMap<Character, Integer> constructMap(char[] ch) {
        // TODO Auto-generated method stub
        HashMap<Character, Integer> map=new HashMap<Character, Integer>();
        for(int i=0;i<ch.length;i++) {
        if(!map.containsKey(ch[i])) {
            map.put(ch[i],0);
        }else {
            map.put(ch[i], map.get(ch[i])+1);
        }
        }
        return map;
    }
}

score 0 · Answer 4 · answered Nov 23 '20 at 17:02

For every character in String1 enter a key value pair in HashMap, where key will be the character and value will be its count. Then for String2 iterate over its characters, if character is present in HashMapdecrement the count associated with that character, else return false. In the end check if any of the key in HashMap has value more than 0, if yes return false. Return true in the end.

Code in groovy:

    def checkIfAnagram(String s1, String s2){
      if(s1.length()!=s2.length())
        return false
    
      HashMap<String,Integer> dict = new HashMap<String,Integer>();
      for(String s:s1.split("")){
        if(dict[s]){
            dict[s] = dict[s]+1;
        }
        else{
            dict[s] = 1;
        }
      }
    
      for(String s:s2.split("")){
        if(!dict[s]){
            return false
        }
        else{
            dict[s] = dict[s]-1; 
        }
      }
    
      dict.each{ key,value ->
        if(value > 0){
            return false
        }
      }
      return true;
    
    }
    
    print(checkIfAnagram("Hello", "olleH"))

Finding anagram using hashmap

4 Answers4

Linked