gXa's blog

Interview Question

By gXa, history, 7 years ago, In English

This is word search problem but constraints seem to be quite strict. Can somebody help with a solution which could pass time limit?

Find Word in Grid

Tags dfs, dp
  • Vote: I like it
  • +18
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How about dp[x][y][i] where (x,y) is the position in the grid and i is the position in the word you're searching? Number of states per word is at worst 100*100*30, transition is 4, which means you'll be able to handle a bunch of maximal words, around 200 or so. Or is the input bigger?

EDIT: I didn't read the problem correctly, "Each grid cell can only be used once." Sorry, thinking on how to fix that.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No input is same. Can you help in code or more detailed explanation for this?

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    How do you handle not using some cell more than once?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That limit sounds very similar to the longest path problem, for which no polynomial solution is known. I personally doubt we can avoid something exponential on the word's length.

      Given that it's a recruitment problem, maybe we can assume that words are indeed English and therefore we're ok with some heuristics appended to dp+backtracking?

      → Reply