In the classic version(k = 1, solve for best path), the key insight used is as follows.
1) In computing best path for cell (i, j) (best[i][j] is the cost of best path from top-left to (i, j)), we notice that this path could either come from it's left or upper neighbor. Thus we do (leaving aside corner cases for a moment)
best[i][j] = min(best[i][j-1], best[i-1][j]) + value[i][j]
2) Now, if we want to compute k best paths from top-left corner to (i, j), we can again follow a similar, but more general technique. Here, best[i][j] can be thought of as a list of k best paths instead of one best path.
best[i][j] = merge_and_select_k(best[i-1][j], best[i][j-1], k)
merge_and_select_k takes two input lists, an integer k - It concatenates the two lists and keeps only the k best values. Of course, you must also add value[i][j] to all these selected items.
3) Loop over the matrix, just like in the classic version and compute best[i][j] for every i and j. Your final result is best[n][n][k].
4) This works because, we only need to consider best[i-1][j] and best[i][j-1] for computing best[i][j]. Time complexity is O(k * n * n) and space complexity is O(k * n), as we only need keep the values for current and previous rows.
Best Answer
I did something similar time ago. You should take advantage of the fact that words are a ordered set of characters. So, you perform a linear search over the matrix for the first letter, then you recursively call the directional search.
To simplify computational complexity you can add some constraint, eg,
if word.length > number of characters on that direction don't start searching.The recursive function signature would be like:
with terminal case
and the search being
This algorithm also cover palindrome cases and words including their syllables.