daily coding problem #63: find word in a 2D matrix scanning left-to-right, top-to-bottom

readme.md

Good morning! Here's your coding interview problem for today.

This problem was asked by Microsoft.

Given a 2D matrix of characters and a target word, write a function that returns whether the word can be found in the matrix by going left-to-right, or up-to-down.

For example, given the following matrix:

[['F', 'A', 'C', 'I'],
 ['O', 'B', 'Q', 'P'],
 ['A', 'N', 'O', 'B'],
 ['M', 'A', 'S', 'S']]

and the target word 'FOAM', you should return true, since it's the leftmost column. Similarly, given the target word 'MASS', you should return true, since it's the last row.

Questions

can matrix be empty? assuming no can an array be empty? assuming no can matrix be inbalanced? assuming no can word to search exceed the length of array? Yes

Thoughts

function returns true or false e.g. FOAM loop through matrix, loop through each array to try and find first letter (F) once I have first letter, get the matrix array index, get the array index.

Once I have the matrix array index and the array index. I want to take the length of the word to search. The length of the word is:

• the upper bound of the current matrix array index through every array in that matrix up to the length (this is the search from top to bottom)
• the upper bound of the array index up to the length (this is the search from left to right)

I can take each word to search and convert into an array for comparison later. For example, a string of "FOAM" would become ['F', 'O', 'A', 'M'] if I run the code 'FOAM'.split('')

const matrix = [
  ['F', 'A', 'C', 'I'],
  ['O', 'B', 'Q', 'P'],
  ['A', 'N', 'O', 'B'],
  ['M', 'A', 'S', 'S']
]

const wordToSearch1 = 'FOAM'
const wordToSearch2 = 'MASS'
const wordToSearch3 = 'QOP'

console.log(wordToSearch1, findWord(matrix, wordToSearch1))
console.log(wordToSearch2, findWord(matrix, wordToSearch2))
console.log(wordToSearch3, findWord(matrix, wordToSearch3))




function findWord(matrix, wordToSearch) {
  //e.g. FOAM
  const wordLength = wordToSearch.length  //4
  const wordArray = wordToSearch.split('')  //['F', 'O', 'A', 'M']
  const firstLetterToSearch = wordToSearch[0] //F


  for (let i = 0; i < matrix.length; i++) {
    
    const currentArray = matrix[i]
    const arrayIndexOfFirstLetter = currentArray.indexOf(firstLetterToSearch)
    if (arrayIndexOfFirstLetter == -1) {
      //we dont have a F in this array
      continue
    }

    //search across
    if (currentArray.length - arrayIndexOfFirstLetter >= wordLength) {
      //we have an F and the array length is long enough
      const possibleWordArrayFound = currentArray.slice(arrayIndexOfFirstLetter, arrayIndexOfFirstLetter + wordLength)

      if (possibleWordArrayFound.join('') === wordArray.join('')) {  
        return true
      }

    }

    //search down
    if (matrix.length - i >= wordLength) {
      //we have a F and the matrix length is long enough

      let possibleWordArrayFound = []

      for (let j = 0; j < wordLength; j++) {
        possibleWordArrayFound.push(matrix[i + j][arrayIndexOfFirstLetter])
      }


      // console.log('here', JSON.stringify(possibleWordArrayFound))
      if (possibleWordArrayFound.join('') === wordArray.join('')) {
        return true
      }

    }


  }

  return false
}