Algo for solving crosswords
I just went over this question and I couldn't think of any better approach for others than bruteforce. Given a 2D array of characters and a raw list of valid words. 1) Find all valid words from the array. From each element in the array, you can move up, down, right, or left. For example,
g o d b o d y
t a m o p r n
u i r u s m p
valid words from the above 2D array -> god, goat, god, cupid, ....
source to share
Make sure you have an alphabetically sorted list of valid words. You can build this n lg n times.
Now that you have this sorted list, you can check if the sequence of characters is the start of the correct word lg n times.
Use a set of valid words to check if a sequence of letters is a valid word (in constant time).
Now call getWords (input, startX, startY, new ArrayList (), "") for each run and merge the resulting lists:
public List<String> getWords(char[][] input, int x, int y, List<String> result, String current){
if(isValidWord(current))
result.add(current);
if(isValidStartOfWord(current)){
// call getWords recursively for all valid directions, concatenating the char to current
}
return result;
}
So you will find your answer in O (x ^ 2 * y ^ 2 * lg w) time with the x and y sizes of the char array and w the size of a valid wordlist. This is no better than the worst case (given the lg w validation), but it doesn't seem possible to me. The expected lead time is better.
If the list of valid words is small, you can also create a set for all valid starts of the correct word. In this case, you can check at constant time if you are on the right track and the worst case comes down to O (x ^ 2 * y ^ 2).
Good luck.
source to share
You have to preprocess this list in the prefix tree than use brute force search in a 2D array above the prefix tree.
You can also use memoization for already parsed array paths and similarly typing part of a word
Reminder example:
RecursiveMatch(i,j,wordPart)
if ((i,j,wordPart) in cache)
print cache[i,j,wordPart]
return;
if a[i,j] on the prefixTreePath){
cache[i,j,wordPart]+=RecursiveMatch(i+1,j,wordPart[1:])
cache[i,j,wordPart]+=RecursiveMatch(i-1,j,wordPart[1:])
cache[i,j,wordPart]+=RecursiveMatch(i,j+1,wordPart[1:])
cache[i,j,wordPart]+=RecursiveMatch(i,j-1,wordPart[1:])
print cache[i,j,wordPart]
}
I haven't added any end-cases for example. borders, easy to add. My intention was to give you a general idea.
source to share
One algorithm depends on a suitable data structure called a prefix tree, or tree .
The first step is to preprocess the dictionary of valid words and place them in the trie. This allows you to efficiently answer a question like this:
Does the given prefix provide a valid prefix?
You can answer this question O(lenght of the prefix)
using trie.
Then suppose you have chosen the starting square for the word. Now you need to traverse the grid in 4 directions and check if the prefix you received so far is a valid prefix. If you are not, you will not go further in that direction. On the other hand, if the prefix is still a valid word, you can simply print it out. The move can be done with either DFS or BFS (it doesn't really matter). The important part is using trie to quickly find valid prefixes and correct words.
source to share