CODEWITHSUNDEEP
algorithmdata-structures
kamal
kamal

Reputation: 2398

Algo to Solve Crossword Puzzle

I just came through this question , and I could not think any better approach for other than bruteforce Given a 2D array of chars and a raw list of valid words. 1) Find all the valid words from the array. From each element in the array, you can traverse up, down, right or left. Eg,

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, godbody, amour,....

Upvotes: 3

Views: 3083

Answers (3)

Jos
Jos

Reputation: 1089

Make sure you have an alphabetically sorted list of valid words. You could build this in n lg n time.

Now you have this sorted list, you could verify if a sequence of characters is a start of a correct word in lg n time.

Use a set of valid words to validate if a sequence of letters is a valid word (in constant time).

Now call getWords(input, startX, startY, new ArrayList(), "") for every startposition 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;
 }

This way you will find your answer in O(x^2 * y^2 * lg w) time, with x and y dimensions of char array and w the size of the valid word list. That is not better than worst case (given the lg w validation), but that does not seem possible to me. The expected runtime is better this way.

If the list of valid words is small, you could also build a set for all valid starts of a correct word. In that case, you could verify in constant time if you are on your way to a correct word, and worst case is reduced to O(x^2 * y^2).

Good luck.

Upvotes: 1

Michael
Michael

Reputation: 2867

You should pre-process this list into a prefix tree, than use brute force search in the 2D array over the prefix tree.

You may also use memoization for already processed paths of the array and similar input of a word part

Memoization 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 e.g. borders, it is easy to add. My intention was to give you the general idea.

Upvotes: 1

Petar Ivanov
Petar Ivanov

Reputation: 93080

One algorithm depends on a suitable data structure called prefix tree or tree.

The first step is to preprocess your dictionary of valid words and put them in the trie. This allows you to efficiently answer question like this one:

Does a given prefix is a valid prefix?

You can answer this question in O(lenght of the prefix) time using the trie.

Then suppose you have chosen the starting square for a word. You need to now traverse the grid in the 4 directions and check if the prefix obtained so far is a valid prefix. If it is not then you will not traverse further in this direction. On the other had if the prefix so far is a valid word, you can just print it. The traversing can be done either using DFS or BFS (doesn't really matter). The important part is to use the trie to check for valid prefixes and valid words fast.

Upvotes: 0

Related Questions