Find all words in the dictionary

Question

I am trying to write a program that will find all the words that can be built on it using a dictionary that was loaded into arrayList from file . sowpodsList is a dictionary stored as an arrayList . I want to iterate through every word in the dictionary, and then compare it with string . Being a string is just a random set of words, how can I do this?

Input: asdm

Conclusion: a, mad, sad .... (any word that matches the dictionary.)

 for (int i = 0; i < sowpodsList.size(); i++) { for (int j = 0; j < sowpodsList.get(i).length(); j++) { if (sowpodsList.get(i).charAt(j) == ) ; } } 

Answer 1

You can search if the number of characters of each word in the dictionary is equal to the value of the input character.

  ArrayList <String> matches = new ArrayList <String> (); // for each word in dict for(String word : sowpodsList) { // match flag Boolean nonMatch = true; // for each character of dict word for( char chW : word.toCharArray() ) { String w = Character.toString(chW); // if the count of chW in word is equal to its count in input, // then, they are match if ( word.length() - word.replace(w, "").length() != input.length() - input.replace(w, "").length() ) { nonMatch = false; break; } } if (nonMatch) { matches.add( word ); } } System.out.println(matches); 

Example output: (the dict file I used here: https://docs.oracle.com/javase/tutorial/collections/interfaces/examples/dictionary.txt )

 Input: asdm Matches: [ad, ads, am, as, dam, dams, ma, mad, mads, mas, sad] 

Answer 2

If I were you, I would change the way you store your dictionary.

Given that the string input contains random letters, what I will do is store all the words in your dictionary in SortedMap<String, char[]> (a TreeMap , to be precise), where the keys are words in your dictionary, and meanings are characters in this word, sorted.

Then I also sorted the characters in the input string and went for it (pseudo code, not tested):

 public Set<String> getMatchingWords(final String input) { final char[] contents = input.toCharArray(); Arrays.sort(contents); final int inputLength = contents.length; final Set<String> matchedWords = new HashSet<>(); char[] candidate; int len; int matched; for (final Map.Entry<String, char[]> entry: dictionary.entrySet()) { candidate = entry.getValue(); // If the first character of the candidate is greater // than the first character of the contents, no need // to continue (recall: the dictionary is sorted) if (candidate[0] > contents[0]) break; // If the word has a greater length than the input, // go for the next word len = candidate.length; if (len > inputLength) continue; // Compare character by character for (matched = 0; matched < len; matched++) if (candidate[matched] != contents[matched]) break; // We only add a match if the number of matched characters // is exactly that of the candidate if (matched == len) matchedWords.add(entry.getKey()); } return matchedWords; } private static int commonChars(final char[] input, final char[] candidate) { final int len = Math.min(input.length, candidate.length); int ret = 0; for (int i = 0; i < len; i++) { if (input[i] != candidate[i]) break; ret++; } return ret; } 

---

With trie: it would also be possible; whether this is practical or not, however this is another question, it depends on the size of the dictionary.

But the basic principle will be the same: you will need a sorted array of characters from the dictionary and add little by little to the trie (use the builder).

A trie node will have three elements:

• a map, where the keys are a set of characters that can be mapped as follows, and the values ​​are the corresponding trie nodes;
• a set of words that can exactly match a node.

You can use your trie implementation of this if you want.

Answer 3

Go to TRIE .

TRIE provides the fastest way to search an array of a large set of words.

https://en.wikipedia.org/wiki/Trie

What you need to do is insert all the words into the trie data structure.

Then you just need to call the search function in Trie to get the logical match information.

Answer 4

There are two ways to do this. The best way depends on the relative size of the data structures.

If the dictionary has a long and short list of letters, it is best to sort the dictionary (if it has not already been), and then build all possible words by rearranging the letters (deleting duplicates). Then do a binary search using string comparisons for each letter combination to find out if these are words in a dictionary. The hard part is that duplicate letters are used only when necessary.

If the list of letters is long and the dictionary is short, in another way it will simply count the number of letters in the input line: two a, one s, one m, etc. Then, for each dictionary of the word if, the number of each individual letter in the dictionary does not exceed the number in the input line, this word is valid.

In any case, add all the words to the output array.