Блог пользователя gXa

Interview Question

Автор gXa, история, 7 лет назад, По-английски

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

Теги dfs, dp
  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      → Ответить