I tried a different approach. I figured that any jumbled word could be converted into an array of characters and sorted. All jumbled words would sort to the same value. For example, "cat" and "tac" both sort to "act".
I used the dictionary you provided and built a map that contains the sorted version of a word as the key. The value associated with each key is the list of all of the words in the dictionary that sort to the key.
Here is the code:
import java.util.*;
/**
* Created by timmattison on 1/6/16.
*/
public class Unjumble {
public static void main(String[] args) {
// Input list
String dict = "cat, rat, mat dog, let, den, pen, tag, art,";
// Clean up the spaces a bit
dict = dict.replaceAll(" ", "");
// Split the words out into an array
String[] dictArray = dict.split(",");
// Create a map to hold our sorted words
Map<String, List<String>> map = new HashMap<>();
// Loop through each word and add it to the map
for (String word : dictArray) {
addWordToMap(word, map);
}
// Find words using our map
findWordsUsingMap("tra", map);
}
private static void findWordsUsingMap(String word, Map<String, List<String>> map) {
String sorted = getSortedWord(word);
List<String> list = map.get(sorted);
// Does this sorted word exist in our map?
if (list == null) {
// No, print no matches and return
System.out.println("No matches for word [" + word + "]");
return;
}
// Yes, it exists. Print the matches.
System.out.println("Found " + list.size() + " match(es) for word [" + word + "]");
for (String match : list) {
System.out.println("- " + match);
}
}
private static void addWordToMap(String word, Map<String, List<String>> map) {
String sorted = getSortedWord(word);
List<String> list = map.get(sorted);
// Does the sorted word exist in our map?
if (list == null) {
// No, create a new list to hold the words that sort to this value
list = new ArrayList<>();
// Add the list to the map
map.put(sorted, list);
}
// Add the word to the list
list.add(word);
}
private static String getSortedWord(String word) {
// From: http://stackoverflow.com/questions/605891/sort-a-single-string-in-java
char[] chars = word.toCharArray();
Arrays.sort(chars);
return new String(chars);
}
}