ContextQMD
Back to Freecodecamp

Challenge 91: Word Search

curriculum/challenges/english/blocks/daily-coding-challenges-javascript/68f6587287ad1f4ad39b0c7d.md

latest2.6 KB
Original Source

--description--

Given a matrix (an array of arrays) of single letters and a word to find, return the start and end indices of the word in the matrix.

  • The given matrix will be filled with all lowercase letters (a-z).
  • The word to find will always be in the matrix exactly once.
  • The word to find will always be in a straight line in one of these directions:
    • left to right
    • right to left
    • top to bottom
    • bottom to top

For example, given the matrix:

md
[
  ["a", "c", "t"],
  ["t", "a", "t"],
  ["c", "t", "c"]
]

And the word "cat", return:

md
[[0, 1], [2, 1]]

Where [0, 1] are the indices for the "c" (start of the word), and [2, 1] are the indices for the "t" (end of the word).

--hints--

findWord([["a", "c", "t"], ["t", "a", "t"], ["c", "t", "c"]], "cat") should return [[0, 1], [2, 1]].

js
assert.deepEqual(findWord([["a", "c", "t"], ["t", "a", "t"], ["c", "t", "c"]], "cat"), [[0, 1], [2, 1]]);

findWord([["d", "o", "g"], ["o", "g", "d"], ["d", "g", "o"]], "dog") should return [[0, 0], [0, 2]].

js
assert.deepEqual(findWord([["d", "o", "g"], ["o", "g", "d"], ["d", "g", "o"]], "dog"), [[0, 0], [0, 2]]);

findWord([["h", "i", "s", "h"], ["i", "s", "f", "s"], ["f", "s", "i", "i"], ["s", "h", "i", "f"]], "fish") should return [[3, 3], [0, 3]].

js
assert.deepEqual(findWord([["h", "i", "s", "h"], ["i", "s", "f", "s"], ["f", "s", "i", "i"], ["s", "h", "i", "f"]], "fish"), [[3, 3], [0, 3]]);

findWord([["f", "x", "o", "x"], ["o", "x", "o", "f"], ["f", "o", "f", "x"], ["f", "x", "x", "o"]], "fox") should return [[1, 3], [1, 1]].

js
assert.deepEqual(findWord([["f", "x", "o", "x"], ["o", "x", "o", "f"], ["f", "o", "f", "x"], ["f", "x", "x", "o"]], "fox"), [[1, 3], [1, 1]]);

--seed--

--seed-contents--

js
function findWord(matrix, word) {

  return matrix;
}

--solutions--

js
function findWord(matrix, word) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const len = word.length;

  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0]
  ];

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      for (let [dr, dc] of directions) {
        let match = true;
        for (let i = 0; i < len; i++) {
          const nr = r + dr * i;
          const nc = c + dc * i;
          if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || matrix[nr][nc] !== word[i]) {
            match = false;
            break;
          }
        }
        if (match) {
          return [
            [r, c],
            [r + dr * (len - 1), c + dc * (len - 1)]
          ];
        }
      }
    }
  }
}