inosvaruag
BAN USERI believe this might be solvable if we view the decisions for the crossword as a tree and do DFS.
Every time we assign a certain word to a certain position, that corresponds to arriving at a node. Any subsequent decisions after this can be viewed as children of this node. The children of this node would need to satisfy two constraints:
1. Required length
2. Same character positions in the word when touching other words already present.
DS for dictionary
1) 1-D array of linked lists where ith row contains all the words which have length i+1
or
2) 2-D array [26][variable length array] of linked lists where [i],[j] contains a list of all words for which i+1'th alphabet lies in position j.
Based on the choice of either data structures, one needs to perform an additional check on character position and length respectively.
Now one can continue traversing the tree till the tree reaches depth of N where N is the total number of words to be filled in crossword.
Isn't the counter-example invalid?
- inosvaruag March 06, 2013When deciding the fate for char[2,1] (zero-based), putting it as part of the row yields 3 characters used and putting it as part of the column puts usage as 5 characters used - the greedy choice in this example points to the optimal solution.