6
\$\begingroup\$

I wrote this program which generates anagrams for a given word. The init function will create a dictionary of words. it can be read from a text file or array. Here I'm reading words from an array to create my dictionary. I would like some advice on how to optimize this code or any changes or suggestions needed to improve efficiency of this code is appreciated.

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

public class Solution {

    static Map<String, ArrayList<String>> dictionaryMap = new HashMap<String, ArrayList<String>>();

    private void addToMap(String key, String word) {
        ArrayList<String> anagramList = dictionaryMap.get(key);

        if (anagramList == null) {
            anagramList = new ArrayList<String>();
            anagramList.add(word);
            dictionaryMap.put(key, anagramList);

        }
        if (!anagramList.contains(word)) {
            anagramList.add(word);
            dictionaryMap.put(key, anagramList);
        }
    }

    private String createMap(String word) {
        Map<Character, Integer> characterCountMap = new HashMap<Character, Integer>();
        StringBuffer buff = new StringBuffer();
        char arr[] = word.toLowerCase().toCharArray();
        Arrays.sort(arr);
        String sortString = Arrays.toString(arr);
        for (int i = 0; i < sortString.length(); i++) {
            char c = sortString.charAt(i);
            if (characterCountMap.containsKey(c))
                characterCountMap.put(c, characterCountMap.get(c) + 1);
            else
                characterCountMap.put(c, 1);
        }

        for (Map.Entry<Character, Integer> entry : characterCountMap.entrySet())
            buff.append(entry.getKey() + entry.getValue());

        return buff.toString();
    }

    private Map<String, ArrayList<String>> init(String[] words) {
        for (String word : words) {
            addToMap(createMap(word), word);

        }
        return dictionaryMap;
    }

    private String[] getAnagrams(String word) {

        String key = createMap(word);
        List<String> al = dictionaryMap.get(key);
        String[] arr = al.toArray(new String[al.size()]);
        return arr;
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println("This is a debug message");
        String arr[] = { "ate", "eat", "THIS", "EAT" };
        obj.init(arr);
        for (String anagram : obj.getAnagrams("tea"))
            System.out.println(anagram);

    }
}
\$\endgroup\$
  • \$\begingroup\$ Are you generating only exact anagrams or can an anagram consist of two or more words? \$\endgroup\$ – TorbenPutkonen Nov 30 at 7:38
  • \$\begingroup\$ Welcome to Code Review. It seems me for every word you create a key in your map concatenating ascii code of chars and the number of occurrences after sorting and then anagrams have the same representation, could you give more informations about this algorithm? \$\endgroup\$ – dariosicily Nov 30 at 9:38
6
\$\begingroup\$

Thanks for sharing your code.

This is what I think about it

General Coding

program against interfaces

Most of your variables are defines as concrete types (classes you actually instantiate). You should better declare them as interface types so that it is possible to exchange the concrete implementation without changing the code all over.

example

static Map<String, ArrayList<String>> dictionaryMap = new HashMap<String, ArrayList<String>>();

should better be

static Map<String, List<String>> dictionaryMap = new HashMap<String, ArrayList<String>>();

or even

static Map<String, Collection<String>> dictionaryMap = new HashMap<String, ArrayList<String>>();

Problem here is that you need to know what interfaces are available and what the consequences are using them. The public API is the place to find that information.

Be consistent

Choose the same approach for the same problem

E.g. you use two different types of loops

    for (int i = 0; i < sortString.length(); i++) {
        char c = sortString.charAt(i);
    //...
    // vs.
    for (String word : words) {
        addToMap(createMap(word), word);
    //...

Unless you really need the index variable for something else then accessing the actual object in the collection loops over you could (and should) stick to the foreach form

    for (char c : sortString.toCharArray()) {

Learn about the capabilities of the objects provided by the runtime

Especially the class Map has some interesting methods your code could benefit from: The code

    ArrayList<String> anagramList = dictionaryMap.get(key);
    if (anagramList == null) {
        anagramList = new ArrayList<String>();
        anagramList.add(word);
        dictionaryMap.put(key, anagramList);
    }

could be replaced by

    ArrayList<String> anagramList = dictionaryMap.computeIfAbsent(key,()->new ArrayList<String>());

If you would know that beside (Array-)List which allows duplicates, the Java Runtime provides another collection type Set which does not hold duplicates, then you could even get rid of the other if in this method too:

static Map<String, Collection<String>> dictionaryMap = new HashMap<String, Collection<String>>();

private void addToMap(String key, String word) {
    dictionaryMap.computeIfAbsent(key,()-> new HashSet<String>())
                 .add(word);
 }

Avoid arrays

instead of arrays better use Collection types like any implementations of the List and Set interfaces. They are more flexible and prevent you to copy data (yourself) when its size needs to be changed.

use the static key word with intention

You declared the variable dictionaryMap as a class variable although it is not accessed by any static method. Unless you understand the consequences you should not use the static key word.

narrow your interfaces

Your method init() has a return value which is not needed since there is no caller of this method dealing with this return value. Methods with return value usually are harder to refactor. Especially its harder to split them into smaller methods.

Naming

Finding good names is the hardest part in programming, so always take your time to think about the names of your identifiers

Please read (and follow) the Java Naming Conventions.

This does not only apply to the casing of the identifiers. It also applies to how names are "constructed". E.g.: you named a method getAnagrams(). By conventions the prefix get is reserved for methods, that do not do any processing but simply return a property of the object. But your method does a lot more than that. Therefore a better name could be findAnagramsOf(String word).

avoid single character names

Since the number of characters is quite limited in most languages you will soon run out of names. This means that you either have to choose another character which is not so obviously connected to the purpose of the variable. And/or you have to "reuse" variable names in different contexts. Both makes your code hard to read and understand for other persons. (Keep in mind that you are that other person yourself if you look at your code in a few month!)

On the other hand in Java the length of identifier names is virtually unlimited. There is no penalty in any way for long identifier names. So don't be stingy with letters when choosing names.

Choose your names from the problem domain

Some of your identifiers (or at least parts of them) have technical meaning. But your identifiers should convey you business solution.

example: characterCountMap, c, sortString or arr.

Remember that the technical details may change while the meaning of your identifiers in respect to the business problem will remain. so this identifiers might better be:

characterCounts, currentCharacter, sortedCharacters or wordCharacters.

\$\endgroup\$
  • 1
    \$\begingroup\$ I believe getOrDefault isn't the right method you want to use. getOrDefault doesn't write the value back into the map. It should be computeIfAbsent. \$\endgroup\$ – RoToRa Dec 1 at 20:36
  • \$\begingroup\$ @RoToRa yes, you're right. Thanks for spotting that. I updated the answer. \$\endgroup\$ – Timothy Truckle Dec 2 at 22:04
  • 1
    \$\begingroup\$ It isn't quite right yet. You still have an getOrDefault example and also the second argument of computeIfAbsent needs to be a Supplier<> (() -> new ArrayList<String>() or ArrayList<String>::new) \$\endgroup\$ – RoToRa Dec 3 at 9:52
2
\$\begingroup\$

Your code is quite complicated. It's possible to do it in a much simpler way. But to do that, you have to know a trick about anagrams:

Iff two words are anagrams of each other, their sorted characters are the same.

This means that you don't need to count each character in a map, you can just take a string, sort its characters (like you already do), make it a string again (which you also do) and use this string as the key to the map.

When you abstract the problem further, it can be seen as a map, in which multiple entries can be stored for each key. This is also something that your code already does. The crucial point is how the key is calculated. You already defined a method for that and called it createMap. That name is wrong. That method does not create a map, it computes the key instead.

Your key generation method should be as simple as:

private String key(String word) {
    char[] chars = word.toLowerCase().toCharArray();
    Arrays.sort(chars);
    return new String(chars);
}

One area where you can improve your code a lot is how you name the variables. Right now you named most of the variables based on their type. For example, al is a list. It probably was an ArrayList somewhere in the past, that's where the a might originate from. Or the a means anagram, in which case the variable should really have been called anagrams.

In general, variable names should represent the purpose of the variable, not the data type. The data type is easy to see if you have a good editor, but the purpose is much more important to express.

\$\endgroup\$
1
\$\begingroup\$

Let's start from beginning: you defined a class Solution containing a map like below:

public class Solution {
    static Map<String, ArrayList<String>> dictionaryMap = new HashMap<String, ArrayList<String>>();
}

With the use of ArrayList the map can contains duplicates of string : to avoid this issue you can use a Set and specifically a TreeSet because when you iterate over keys, they are ordered by their natural ordering. So the class can be rewritten like below:

public class Solution {
    private Map<String, Set<String>> map;

    public Solution() {
        this.map =new TreeMap<>();
    }
}

Once you defined the class in this way you can define two methods addWords and addWord to add words to your dictionary like below:

public void addWords(String[] words) {
    for (String word : words) {
        addWord(word);
    }
}

private void addWord(String word) {
    String key = generateKey(word);

    if (!map.containsKey(key)) {
        map.put(key, new TreeSet<String>(Arrays.asList(word)));
    } else {
        Set<String> set = map.get(key);
        set.add(word);
    }
}

You can check inside the method addWord the method generateKey is called to generate the key corresponding to the word you are trying to include in your dictionary; if the key is not already contained in your map a new TreeSet containing the word will be created and associated to the key in the map, otherwise the word is an anagram of a word already present in the dictionary and will be added to the existing TreeSet.

The most important method of the program is the generateKey method that generate a representation of the word you want to insert in your dictionary, I'm using a representation formed by concatenation of chars of word and their occurrences sorted in alphabethic order:

  • "tea" -> a1e1t1
  • "eat" -> a1e1t1

Below the code of the method generateKey;

private static String generateKey(String word) {
    Map<Character, Integer> map = new TreeMap<>();
    StringBuilder builder = new StringBuilder();
    char arr[] = word.toLowerCase().toCharArray();

    for (char key : arr) {
        int value = map.getOrDefault(key, 0);
        map.put(key, ++value);
    }

    Set<Character> set = map.keySet();
    for (Character ch : set) {
        builder.append(ch + Integer.toString(map.get(ch)));
    }

    return builder.toString();
}

You can check I used inside the method a TreeMap to obtain characters keys already naturally ordered, so I don't need to use sort method like your code.

The final method is the method getAnagrams that returns the list of anagrams of the word in a array that can be empty if the word or its anagrams are present in the dictionary (I would prefer this method returns an unmodifiable collection instead of array):

public String[] getAnagrams(String word) {
    String key = generateKey(word);
    Set<String> set = map.getOrDefault(key, new TreeSet<>());
    return set.stream().toArray(String[]::new);
}

Here the complete code of class Solution:

Solution.java

package codereview;

import java.util.Arrays;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

public class Solution {
    private Map<String, Set<String>> map;

    public Solution() {
        this.map =new TreeMap<>();
    }

    public void addWords(String[] words) {
        for (String word : words) {
            addWord(word);
        }
    }

    private void addWord(String word) {
        String key = generateKey(word);

        if (!map.containsKey(key)) {
            map.put(key, new TreeSet<String>(Arrays.asList(word)));
        } else {
            Set<String> set = map.get(key);
            set.add(word);
        }
    }

    private static String generateKey(String word) {
        Map<Character, Integer> map = new TreeMap<>();
        StringBuilder builder = new StringBuilder();
        char arr[] = word.toLowerCase().toCharArray();

        for (char key : arr) {
            int value = map.getOrDefault(key, 0);
            map.put(key, ++value);
        }

        Set<Character> set = map.keySet();
        for (Character ch : set) {
            builder.append(ch + Integer.toString(map.get(ch)));
        }

        return builder.toString();
    }

    public String[] getAnagrams(String word) {
        String key = generateKey(word);
        Set<String> set = map.getOrDefault(key, new TreeSet<>());
        return set.stream().toArray(String[]::new);
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println("This is a debug message");
        String words[] = { "ate", "eat", "THIS", "EAT" };
        obj.addWords(words);
        for (String anagram : obj.getAnagrams("tea"))
            System.out.println(anagram);
    }
}

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.