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

}

Answer 3

Based on the asci approach I have made a working code

public static void main(String[] args) {
        String[] values ={"eat", "tea", "tan", "ate", "nat", "bat"};
        Map<Integer, List<String>> resultMap = new HashMap<Integer, List<String>>();
        for (String value : values) {
            char[] caharacters = value.toLowerCase().toCharArray();
            int asciSum = 0;
            for (char character : caharacters) {
                asciSum = asciSum + (int)character;
            }
            System.out.println(asciSum);
            if(resultMap.containsKey(asciSum)) {
                resultMap.get(asciSum).add(value);
            }else {
                List<String> list = new ArrayList<String>();
                list.add(value);
                resultMap.put(asciSum, list);
            }
        }
        System.out.println(resultMap);
    }

This will give result

{323=[tan, nat], 311=[bat], 314=[eat, tea, ate]}

but if we encounter diff characters with same asci value sum like 10+11 = 20+1 below code will work where based on the sorted string we make the result map

public static void main(String[] args) {
        String[] values ={"eat", "tea", "tan", "ate", "nat", "bat"};
        Map<String, List<String>> resultMap = new HashMap<String, List<String>>();
        for (String value : values) {
            char[] caharacters = value.toLowerCase().toCharArray();
            Arrays.sort(caharacters);
            String sortedValue = new String(caharacters);
            System.out.println(sortedValue);
            if(resultMap.containsKey(sortedValue)) {
                resultMap.get(sortedValue).add(value);
            }else {
                List<String> list = new ArrayList<String>();
                list.add(value);
                resultMap.put(sortedValue, list);
            }
        }
        System.out.println(resultMap);
    }

This will return

{aet=[eat, tea, ate], abt=[bat], ant=[tan, nat]}

I have fixed the comments and edits provided.

Answer 4

Here's my idea, first I would create a class that will store the original string and it's sorted version:

class Anagram {
   String s;
   String sorted;
}

Then I map the input to my list of Anagram:

List<Anagram> collect = Arrays.stream(strs)
            .map(a -> new Anagram(a, Arrays.stream(a.split(""))
                    .sorted()
                    .reduce(String::concat).get()))
            .collect(Collectors.toList());

Then I just group the obtained list by sorted string:

 Map<String, List<Anagram>> groupBy = collect
             .stream()
             .collect(Collectors.groupingBy(Anagram::getSorted));

Now you have the lists with grouped anagrams, just extract from them the original string:

List<List<String>> result = new ArrayList<>();

for(List<Anagram> list : collect1.values()) {
     List<String> myList = list.stream().map(Anagram::getS).collect(Collectors.toList());
     result.add(myList);
}