Count Grid Words with One Turn
Updated
Problem statement
grid is a rectangle of lowercase letters given as strings of equal length; grid[r][c] is the letter at row r, column c. words holds the lowercase words to look for.
A trace of a word is a list of cells, one per letter, that spells the word in order. For a word of one letter, the list is just one cell holding that letter, and there is no heading to choose. For longer words, the list must also obey these rules:
- Consecutive cells of a trace share a side, so they are vertical or horizontal neighbors.
- A trace starts with one heading and keeps it. At one cell of its choice it may switch, once, to a different heading, and it keeps that heading to the end.
- The new heading may point straight back, so a cell can appear in a trace twice.
Two traces are counted separately whenever their cell sequences differ. Return an array where entry i counts the traces of words[i].
Function
countWordPaths(grid: String[], words: String[]) → int[]Examples
Example 1
grid = ["ab","cd"]words = ["abd","abdc","aba"]return = [1,0,1]The cells are a (row 0, column 0), b (0, 1), c (1, 0) and d (1, 1). "abd": a then b heads right, and the one switch, to heading down, reaches d, so its count is 1. "abdc": after a, b, d the heading would have to change a second time to reach c, so its count is 0. "aba": a then b, and the switch points straight back to a, so its count is 1.
Example 2
grid = ["sun","nod","use"]words = ["nun","u","sus","dos"]return = [2,2,2,1]The rows are s u n, n o d and u s e. "nun": from the n at (0, 2), step left to u and turn back right; from the n at (1, 0), step down to u and turn back up. That is 2, one in a row and one in a column. "u": one letter, so each of the 2 cells holding u is one trace. "sus": (0, 0) to (0, 1) and back, and (2, 1) to (2, 0) and back, so 2. "dos": from d at (1, 2), left to o, then the one switch heads down to s, so 1.
Example 3
grid = ["plan","atee","sent"]words = ["planet","ten","ene"]return = [1,3,5]"planet" has 6 letters, more than any row (4) or column (3) holds, so a trace must bend. The only one runs right along row 0 to the n at (0, 3), then down column 3 through e and t. That gives 1. "ten": the t at (1, 1) has two bent traces, down to the e at (2, 1) then right to the n at (2, 2), or right to the e at (1, 2) then down to the same n. The t at (2, 3) has one straight trace, up column 3 through e and n. That is 3. "ene": from the e at (1, 2), go down to the n at (2, 2), then either back up to (1, 2) or left to the e at (2, 1). From the e at (2, 1), go right to the same n, then either back left to (2, 1) or up to the e at (1, 2). From the e at (1, 3), go up to the n at (0, 3) and back down. The bend (1, 2), (2, 2), (2, 1) and its reverse use the same three cells in a different order, so they count as two traces, and the total is 5.
Constraints
1 <= grid.length <= 301 <= grid[i].length <= 30, and every row has the same length.1 <= words.length <= 201 <= words[i].length <= 20gridandwordscontain only lowercase English letters.
More Capital One Online Assessment questions
- Rank Football TeamsOA · Seen Oct 2026
- Count Subarrays Matching a Comparison PatternOA · Seen Oct 2026
- Arithmetic Triplets After QueriesOA · Seen Oct 2026
- Branch with the Most FilesOA · Seen Oct 2026
- Count One-Swap Number PairsOA · Seen Oct 2026
- Distinct Values on Maximum-Sum FramesOA · Seen Oct 2026
- Earliest Meeting Time for All EmployeesOA · Seen Oct 2026
- Earn the Most 🐝OA · Seen Oct 2026
- Sort Adjacent PairsOA · Seen Oct 2026
- Bouncing Diagonal WeightsOA · Seen Oct 2026
Similar questions at other companies
- Lexicographically Smallest Grid Path with One Letter ChangeInfosys · OAInfosys interview questions
- Maximum Equal-Bit Pairs in a SubsequenceAmazon · OA
- Longest Subsequence That Is a SubstringBooking.com · OA
- Count Digit Replacements with No Equal Adjacent DigitsMicrosoft · OAMicrosoft interview questions
- Grid Paths with Override PassesIMC Trading · OAIMC Trading interview questions
- Palindrome CounterGoldman Sachs · OAGoldman Sachs interview questions
- Largest Square of OnesOpenAI · OAOpenAI interview questions
- Count Straight-Line Word Occurrences in a GridOptiver · OAOptiver interview questions
- Longest String ChainVisa · OAVisa interview questions
- Minimum Moves to Spread Stones Across a GridAmerican Express · OAAmerican Express interview questions
Capital One interview experiences
- Capital One Experienced Engineer Power Day and OA: 6 Experiences
- Capital One New Grad OA Questions: 14 Experiences (Part 2 of 2)
- Capital One TDP Agentic Round (AI Coding): 7 Experiences
- Capital One SWE Power Day, Level Not Reported: 6 Experiences
- Capital One TIP Intern OA and Power Day: 13 Experiences
- Capital One TDP Agentic Power Day: 25 Experiences (Part 1 of 2)