Anagrams finding in java

Question

I stuck on a problem. I have a String array which is consist of String[]={"eat", "tea", "tan", "ate", "nat", "bat"} Now, I should segregated those word which have same letter on it and make a group. eat,tea,ate they have same letter in each word so this is a group. Group 2 should be tan,nat and Group3 should be bat. So I have to make a list of list to store those groups.

My approach:

To solve this problem I first find out the ascii values of each letter and then add those ascii values for a word. Like eat find out the ascii values of e,a,t and add them. I take this approach because if the letters are repeated in the words then they must have same ascii sum. After that I group them same Ascii sums and find out which words have those sums then they belongs to same group.

My progress I find out ascii sums and put them in a hashmap. But then I could not group the same values. As I failed to group the ascii values I cannot find out the words.I have no clue how to proceed.

I also follow this posts

post1 post2

But there approach and my approach is not same. Also the questions are different from mine. I am discussing here about a different approach which is depend upon ASCII values.

My code:

public List<List<String>> groupAnagrams(String[] strs) {
    ArrayList<Character>indivistr=new ArrayList<>();
    ArrayList<Integer>dup=new ArrayList<>();
    HashMap<Integer,Integer>mappingvalues=new HashMap<>();
    for(int i=0;i<strs.length;i++){
        int len=strs[i].length();
        int sum=0;
        for(int j=0;j<len;j++){
            indivistr.add(strs[i].charAt(j));
            int ascii=(int)strs[i].charAt(j);
            sum=sum+ascii;

        }
        mappingvalues.put(i,sum);

    }

}

One more approach I transfer the map keys in a Arraylist and map values in a ArrayList. Something like that,

ArrayList<Integer>key_con=new ArrayList< (mappingvalues.keySet()); ArrayList<Integer>val_con=new ArrayList<>(mappingvalues.values());

Then using two loops and put the same values into another list.

for(int k=0;k<val_con.size();k++){
        for(int k1=k+1;k1<val_con.size();k1++){
            if(val_con.get(k).equals(val_con.get(k1))){
                dup.add(val_con.get(k1));
            }
        }

Now if I print dup output will be [314, 314, 314, 323] which is partially correct. It should be 314,314,314,323,323,311

Answer 1

This should get you started.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Main {

    public static void main(String args[]) throws Exception {

        String[] words ={"eat", "tea", "tan", "ate", "nat", "bat"};

        for(List<String> list : groupAnagrams(words))
            System.out.println(list);

    }

    public static List<ArrayList<String>> groupAnagrams(String[] words) {

        List<ArrayList<String>> wordGroups = new ArrayList<ArrayList<String>>();
        HashMap<Integer, ArrayList<String>> map = new HashMap<Integer, ArrayList<String>>();

        for(String word : words) {

            int sum = 0;
            for(char c : word.toCharArray())
                sum += c;
            if(map.containsKey(sum))
                map.get(sum).add(word);
            else {
                ArrayList<String> list = new ArrayList<String>();
                list.add(word);
                map.put(sum, list);
            }

        }

        for(ArrayList<String> list : map.values())
            wordGroups.add(list);

        return wordGroups;
    }
}

This program will work for small scale things such as this but consider the following input data:

{"a", "@!"}

The sum of these Strings are both 97.

Since you're using ASCII values to find anagrams you might run into a case such as this. This isn't a particularly pressing matter until you start messing around with lowercase letters and capitals. Easy fix for that is just a String.ToUpperCase() and map the symbols to huge numbers and you're good to go.

Answer 2

For posterity:

public class anagrams {
public static void main(String args[]) {
    int numberOfAnagrams = 0;
    String[] stringArray = {"eat", "tea", "tan", "ate", "nat", "bat", "plate", "knot"};
    List<String> stringList = Arrays.asList(stringArray);

    for(int i = 0; i < stringList.size() - 1; i++) {
        for(int j = i + 1; j < stringList.size(); j++) {
            if(isAnagram(stringList.get(i), stringList.get(j))) {
                System.out.println(stringList.get(i) + " " + stringList.get(j));
                numberOfAnagrams += 2;
            }
        }
    }
    System.out.println(numberOfAnagrams);
}

private static boolean isAnagram(String s1, String s2) {
    // In order for two String to be anagrams, they must have the same length.
    if(s1.length() != s2.length()) {
        return false;
    }
    // If s2 does not contain even one of s1's chars return false.
    for(int i = 0; i < s1.length(); i++) {
        if(!s2.contains("" + s1.charAt(i))) {
            return false;
        }
    }
    return true;
}

}