Trace a Word Through a Letter Grid
Updated
Problem statement
You are given an m x n grid of letters board and a string word. Return true if you can spell word by walking through the grid, and false otherwise.
A walk starts at any cell whose letter is the first letter of word. Each step moves to a neighbouring cell that shares a side with the current one (up, down, left or right; corners do not count, and the grid does not wrap around), and that cell must hold the next letter of word. A cell can be used at most once in the same walk.
Upper and lower case letters are different: 'a' does not match 'A'.
Function
exist(board: char[][], word: String) → booleanExamples
Example 1
board = [["T","R","I","P"],["O","A","X","S"],["U","R","E","T"]]word = "TRIPS"return = trueStart at the T in the top-left corner and move right through R, I and P, then down to the S below P.
Example 2
board = [["T","R","I","P"],["O","A","X","S"],["U","R","E","T"]]word = "STAR"return = falseThe only S is in row 1, column 3 (counting from 0). The only T next to it is in row 2, column 3, and that T has no A next to it. The other T is not next to an S. Every letter of the word is on the board, but no path spells it.
Example 3
board = [["T","R","I","P"],["O","A","X","S"],["U","R","E","T"]]word = "TOT"return = falseT then O works only from the top-left T down to the O below it. The O has no other T next to it, and the first T cannot be used a second time.
Constraints
m == board.lengthandn == board[i].length1 <= m, n <= 61 <= word.length <= 15boardandwordcontain only English letters, upper and lower case.
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Enumerate Character Paths to a MarkerTesla · ONSITE INTERVIEWTesla interview questions
- Word Search with Eight-Direction AdjacencyMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Find a Word in a Letter GridAdobe · PHONE SCREENAdobe interview questions
- Word SearchBloomberg LP · OA · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Word SearchAmazon · ONSITE INTERVIEW
- Number of Islands with Diagonal ConnectivityGoogle · ONSITE INTERVIEWGoogle interview questions
- Island Count and Maximum AreaOracle · ONSITE INTERVIEWOracle interview questions
- Query Whether an Island Size ExistsMeta · ONSITE INTERVIEWMeta interview questions
- Maximum Number of Fish in a GridGlobalization Partners · ONSITE INTERVIEW
- Max Area of IslandGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)