One Turn Matrix Words
MediumMatrix · Uber
You are given a grid of lowercase letters board and a list of distinct lowercase words.
A word can be spelled with at most one turn if there is a path of cells whose letters, read in order, equal the word, where the path:
- starts at any cell,
- moves only right (same row, next column) or down (next row, same column),
- goes straight in one of those two directions, then optionally switches to the other direction once and goes straight until the end.
So a path is either a straight line going right or down, or an "L": right then down, or down then right. The turn may happen at any cell, including the first or last letter. Cells are never revisited (they cannot be, since you only move right or down).
Return how many of the words can be spelled this way.
Example 1
- Input:
- board = [["c", "a", "t", "s"], ["o", "x", "o", "a"], ["w", "x", "p", "d"]], words = ["cats", "sad", "atop", "caxxp", "dog"]
- Output:
- 3
- Explanation
catsruns straight right along row 0,sadruns straight down column 3, andatopgoes right fromatotthen turns down throughoandp.caxxpwould need right, down, then right again (two turns), anddogis nowhere on the board.
Example 2
- Input:
- board = [["a", "b"], ["c", "d"]], words = ["abd", "acd", "ad", "ba"]
- Output:
- 2
- Explanation
abdis right then down andacdis down then right.adwould need a diagonal move andbawould need to move left, so neither counts.
Example 3
- Input:
- board = [["z"]], words = ["z", "zz"]
- Output:
- 1
- Explanation
- The one-letter word is spelled by the single cell.
zzneeds a second cell, which does not exist.
Constraints
1 <= board.length, board[i].length <= 20- All rows of
boardhave the same length 1 <= words.length <= 1001 <= words[i].length <= 40boardandwordscontain only lowercase English letters;wordsare distinct