Word Search - Find all words - aloalgo
aloalgo logoaloalgo
Beta
Problems
Login

Word Search - Find all words

Hard

You are given a square grid of letters, representing a Boggle board, and a dictionary (a list of valid words).

Your task is to find all unique valid words present on this Boggle board.

Remember that:

  • Words are formed by connecting adjacent letters on the board, either horizontally, vertically, or diagonally.
  • Each letter cell can be used only once when forming a single word.
  • Any word you find must be present in the provided dictionary to be considered valid.

Return a list of all unique valid words found.

Example 1

Inputs
board = [["c", "a"], ["t", "s"]]
dictionary = ["cat", "at", "as", "sat", "cast", "cats", "tas", "acts", "act"]
Output
["act", "acts", "as", "at", "cast", "cat", "cats", "sat", "tas"]
Explanation:
  • at is made by (0,1) -> (1,0)
  • as is made by (0,1) -> (1,1)
  • cat is made by (0,0) -> (0,1) -> (1,0)
  • cats is made by (0,0) -> (0,1) -> (1,0) -> (1,1)
  • act is made by (0,1) -> (0,0) -> (1,0)
  • sat is made by (1,1) -> (1,0) -> (0,1)

Example 2

Inputs
board = [["b", "e"], ["a", "t"]]
dictionary = ["be", "bat", "bet", "eat", "tea", "tab", "ate"]
Output
["ate", "bat", "be", "bet", "eat", "tab", "tea"]
Explanation:
  • be is made by (0,0) -> (0,1)
  • bat is made by (0,0) -> (1,0) -> (1,1)
  • bet is made by (0,0) -> (0,1) -> (1,1)
  • eat is made by (0,1) -> (1,0) -> (1,1)
  • tea is made by (1,1) -> (0,1) -> (1,0)
  • tab is made by (1,1) -> (1,0) -> (0,0)
  • ate is made by (1,0) -> (1,1) -> (0,1)

Example 3

Inputs
board = [["p", "i", "n", "e"], ["l", "p", "p", "a"], ["e", "n", "e", "s"]]
dictionary = ["pine", "pin", "pen", "apple", "pineapple", "pea", "ape", "sap", "sea", "plan", "pan", "lane", "line", "lap", "pal", "nap", "penal", "pane", "pale", "peal", "nil", "nap", "ins", "sin", "sip", "spin", "spin", "pins", "peins"]
Output
["ape", "apple", "line", "nap", "nil", "pan", "pane", "pea", "pen", "pin", "pine", "pineapple", "sap", "sea", "spin"]
Loading...
Case 1Case 2Case 3
Inputs
board = [["c", "a"], ["t", "s"]]
dictionary = ["cat", "at", "as", "sat", "cast", "cats", "tas", "acts", "act"]
Output
["act", "acts", "as", "at", "cast", "cat", "cats", "sat", "tas"]
🤖

Hello! I am your ✨ AI assistant. I can provide you hints, explanations, give feedback on your code, and more. Just ask me anything related to the problem you're working on!