How to compare character input by user to dictionary file in Java?

Question

I need to read the user input and compare this to a dictionary.txt. The user may input any number of characters and the program must return all the words in the English language that can be made from these characters. The letters can be used in any order and may only be used once. For example:

User Input: "odg"

Output: "dog" , "god" ... and any others

After quite a substantial amount of research, I have come up with the following partial solution:

1. Read user input
2. Convert to an array of characters
3. Loop through the document depending on array length
4. Using indexOf to compare each character in this array to each line, then printing the word/s which do not return -1

How do I compare a set of characters inputted by the user to those found in a text file (dictionary) ? The characters do not have to be in any order to match .(as seen in the example used above)

Bear with me here, I know this must be one of the most inefficient ways to do such a task! Any further ideas on how to implement my original idea would be appreciated, while I am also open to any new and more efficient methods to perform this operation.

Below is what I have come up with thus far:

  public static void main(String[] args) throws FileNotFoundException {
    BufferedReader reader1 = new BufferedReader(new FileReader(FILENAME));
    Scanner sc = new Scanner(System.in);
    String line;
    ArrayList<String> match = new ArrayList<>();

    System.out.println("Enter characters to see which english words match: ");
    String userInput = sc.next();

    char arr[]  = userInput.toCharArray();
    int i;

        try {

            while ((line = reader1.readLine()) != null) {

                for (i=0; i < arr.length; i++)
                {
                   if ((line.indexOf(userInput.charAt(i)) != -1) && (line.length() == arr.length)) {
                       match.add(line);
                    }
                    else {
                //        System.out.println("no matches");
                    }
                }

            }
            System.out.println(match);
        }

    catch (IOException e) {

        e.printStackTrace();

    }

**Current results: **

Words in text file:

cab
dog
god
back
dogs
quick

User input: "odg"

Program output:

[god, god, god, dog, dog, dog]

The program should return all words in the dictionary that can be made out of the string entered by the user I am managing to return both instances in this case, however, each are displayed for three times (arr.length).

Answer 1

First of all, interesting question. I implemented my solution and Ole V.V's solution. Here are the codes based on your post. I test the only test case you provided, not sure whether this is what you want. Let me know if it is not working as you expected.

Solution One: counting O(nk)

public static void main(String[] args) throws IOException {
    BufferedReader reader1 = new BufferedReader(new FileReader(FILENAME));
    Scanner sc = new Scanner(System.in);

    System.out.println("Enter characters to see which english words match: ");
    String userInput = sc.next();

    Map<Character, Integer> counter = count(userInput);
    String line;
    while ((line = reader1.readLine()) != null) {
        Map<Character, Integer> lineCounter = count(line);
        if(lineCounter.equals(counter)) {
            System.out.println(line);
        }
    }
}

public static Map<Character, Integer> count(String input) {
    Map<Character, Integer> result = new HashMap<Character, Integer>();
    for (char c: input.toCharArray()) {
        result.putIfAbsent(c, 0);
        result.put(c, result.get(c) + 1);
    }

    return result;
}

Solution Two: sorting O(nk)

public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new FileReader(FILENAME));
    Scanner sc = new Scanner(System.in);

    System.out.println("Enter characters to see which english words match: ");
    String userInput = sc.next();
    userInput = sort(userInput);

    String line;
    while ((line = reader.readLine()) != null) {
        String sortedLine = sort(line);
        if(sortedLine.equals(userInput)) {
            System.out.println(new String(line));
        }
    }
}

// counting sort
public static String sort(String input) {
    char c[] = input.toCharArray();
    int length = c.length;
    char output[] = new char[length];

    int count[] = new int[256];
    for (int i = 0; i < length; i++) {
        count[c[i]] = count[c[i]] + 1;
    }

    for (int i = 1; i <= 255; i++) {
        count[i] += count[i - 1];
    }

    for (int i = 0; i < length; i++) {
        output[count[c[i]] - 1] = c[i];
        count[c[i]] = count[c[i]] - 1;
    }

    return new String(output);
}

Answer 2

The standard solution to this kind of problem is: sort the characters of the user input. So odg will become dgo and back will become abck. For each word in the dictionary, do the same sorting. So cab will become abc and dog will be dgo — hey, that’s the same as the first user input, so now we know that this word should be output.

The strong point with this solution is you make sure every letter is used exactly once. It even takes duplicate letters into account: if the same letter comes twice in the user input, it will only find words that also contain that letter exactly twice.

If you like, you can prepare your word list in advance by building a map where the keys are the alphabetically sorted words and the values are lists of words that contain those same letters. So key dgo will map to a list of [dog, god]. Then you just have to sort the input and make a lookup.

Answer 3

I'll show you a solution that is easy to understand and implement but not the fastest available:

Possible solution: Array sorting

Treat input string and dictionary word as array of chars, sort them, then compare them:

public static boolean stringsMatchSort(String a, String b) {
    // Different length? Definitely no match!
    if (a.length() != b.length()) {
        return false;
    }

    // Turn both Strings to char arrays
    char[] charsA = a.toCharArray();
    char[] charsB = b.toCharArray();

    // Sort both arrays
    Arrays.sort(charsA);
    Arrays.sort(charsB);

    // Compare them, if equal: match!
    return Arrays.equals(charsA, charsB);
}

Note how I made the meat of your program / problem into a method. You can then easily use that method in a loop that iterates over all words of your dictionary. The method doesn't care where the words come from: a file, a collection, additional user input, the network, etc.

It also helps to simplify your program by dividing it into smaller parts, each with a smaller responsibility. This is commonly known as divide & conquer and is one of the most valuable strategies for both, new and old programmers alike, when it comes to tackling complicated problems.

Other solutions: Prime numbers, HashMaps, ...

There are other (including faster and more elegant) solutions available. Take a look at these related questions, which yours is pretty much a duplicate of:

• "How to check if two words are anagrams"
• "finding if two words are anagrams of each other"

Additional notes

Depending on your application, it might be a good idea to first read the dictionary into a suitable collection. This would be especially helpful if you perform multiple "queries" against the same dictionary. Or, if the dictionary is really huge, you could already strip out duplicates during the creation of the collection.