Spellathon solver in Java What is Spellathon?

The rules of Spellathon are as follows:


Create words that have 4 to 7 letters.
Include the center letter in every word.
Form at least one 7-letter word.
Plurals are acceptable.
The dictionary used is in English.


Here is a similar implementation.

The dictionary (word list) I'm using is this.

public class Spellathon {

    private static final Set&lt;String&gt; permutations = new HashSet&lt;&gt;();

    private static void permutation(String str) {
        permutation(str.charAt(0), "", str);
    }

    private static void permutation(char idx, String prefix, String str) {
        int n = str.length();

        if (n != 0) {
            for (int i = 0; i &lt; n; i++) {
                permutation(idx, prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
            }
        }

        if(prefix.length() &gt; 3 &amp;&amp; prefix.indexOf(idx) &gt;= 0) {
            permutations.add(prefix);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String letters;

        System.out.print("Input: ");
        letters = sc.nextLine();

        permutation(letters);

        try {
            for(String x: permutations) {
                Scanner scFile = new Scanner(new File("words.txt"));

                while(scFile.hasNextLine()) {
                    String cur = scFile.nextLine();
                    if(cur.equalsIgnoreCase(x)) {
                        System.out.println("Found: " + cur);
                    }
                }
            }
        } catch (FileNotFoundException ex) {
            System.out.println("Word list file Not Found.");
        }
    }
}


Input: Pass the given letters as a String with the central letter as the first letter. The other letters can be in any order.

Output:



Input: elolh
Found: Hell
Found: hell
Found: Lole
Found: hello
Found: Holle
Found: Hole
Found: hole


I don't mind the redundant occurrences. My issue is that the code takes a lot of time to execute (that is why, I used 5 letters as an example).

Any comments/answers that can help reduce the execution time will be appreciated. Also, if anyone review the overall correctness of the program, it will be helpful.
The explanation for slowness is simple: you're doing a slow operation (reading a file) many many times (due to combinatorial explosion).

How many permutations of "hello" are there? For 5 items, there are 5!, or 120 permutations. However, two of the letters are indistinguishable, so it's actually \$\frac{5!}{2!}\$, or 60. Add the 12 permutations of "hell", 24 permutations of "helo", and 12 permutations of "hllo", and we have about a hundred.

Of those, I would expect only maybe a dozen to be valid English words.

Then, for each permutation, you are opening the file and reading every line to see if the candidate is a word. File IO involves the operating system and the disk — both very expensive.



Generating all permutations of something is costly. In contrast, checking whether two given words are permutations of each other is a simple matter of counting.

A smarter approach, therefore, would be to go through the dictionary once, and check whether each word meets the acceptance criteria.