JavaScript Brute Force Solution


  • 0
    J

    Preparation

    First we need to define which characters exist in each row of the keyboard (letters only). Let's start by defining an array:

    var keyboard = [
      'QWERTYUIOPqwertyuiop'.split(''),
      'ASDFGHJKLasdfghjkl'.split(''),
      'ZXCVBNMzxcvbnm'.split('')
    ]
    

    Other solutions I have seen convert each letter or word to upper case before comparing to an upper case set. I included both upper and lower cases in the arrays because I think calling .toUpperCase() for each iteration is unnecessary. If it happens to be faster to do it the other way, I will eat my hat (I don't have a hat).
    We attach a split('') here (converting the string to an array of characters) so that later on we can determine whether a character exists in the set by calling keyboard[row].indexOf(character) > -1

    Next we move on to the solution function itself.

    Function

    Let's declare an empty array to hold all of our results

    var findWords = function(words) {
      var results = []
    

    then form our initial loop through words

    for (var i = 0; i < words.length; i++) {
      if (words[i].length === 1) results.push(words[i])
      var currentRow = -1
      var w = words[i].split('')
    

    The if here is included so that a words[i] with only one character pushes to results straight away (a one letter word can always be typed using one row). Our following logic does not cover this case, so we just get it out of the way at the start.

    I have set currentRow = -1 so that we can switch between first-run logic and subsequent logic.

    Now, for each word (words[i]), we need to loop through each letter in the word. Split the word into an array of characters

    var w = words[i].split('')
    

    and then start in on the loop

    for (var j = 0; j < w.length; j++) {
    

    Logic

    Before we move on to the logic we have to think about how we will approach flow. Earlier we set the variable currentRow = -1 and now we will see why. The first iteration over a word must always take the first path because the row has not yet been set. Once we have compared the first letter, then we know what row it lives in and can compare following letters to only that row. Keep in mind that we could just as easily have set the initial value of currentRow to undefined or null (or really any other value besides the integers 0 though 2) and used if (!currentRow). currentRow values 0-2 are reserved for the indexes of the keyboard array.

    if(currentRow < 0) {
    

    The next group of logic determines exactly which row of the keyboard the first character of word[i] belongs to. Array.prototype.indexOf() will return a positive integer index of the paramater if it exists, otherwise it will return -1. We can use this 'doesn't exist' return value to our advantage. We know that if keyboard[currentRow].indexOf(w[j]) returns any value equal to or greater than 0 it exists in the array.

    if (keyboard[0].indexOf(w[j]) > -1) { 
      currentRow = 0
    } else if (keyboard[1].indexOf(w[j]) > -1) {
      currentRow = 1
    } else if (keyboard[2].indexOf(w[j]) > -1) {
      currentRow = 2
    }
    

    Now that we know which row the first character is in, it is a simple matter of checking that all of the remaining characters in word[i] exist in keyboard[currentRow].

    } else {
      if (keyboard[currentRow].indexOf(w[j]) === -1) {
        break
      } else if (keyboard[currentRow].indexOf(w[j]) > -1 && j === w.length -1)
        results.push(words[i]
      }
    

    Here we check first if the character is in the row and, if not, we jump right out of the iteration. Then we check if the character is both in the row and if it is the last step of the loop. If it is not the last step, the loop simply continues (even without an else continue statement). If it is the last step, and the character is in the row, we now know that the word is good, so we push it to our array result.

    Lastly, we return the array

    return result
    

    Solution

    var keyboard = [
      'QWERTYUIOPqwertyuiop'.split(''),
      'ASDFGHJKLasdfghjkl'.split(''),
      'ZXCVBNMzxcvbnm'.split('')
    ]
    
    var findWords = function(words) {
      var results = []
      for (var i = 0; i < words.length; i++){
        if (words[i].length === 1) {
          results.push(words[i])
        }
        var currentRow = -1
        var w = words[i].split('')
        for (var j = 0; j < w.length; j++) {
          if ( currentRow < 0) {
            if (keyboard[0].indexOf(w[j]) > -1) {
              currentRow = 0
            } else if (keyboard[1].indexOf(w[j]) > -1) {
              currentRow = 1
            } else if (keyboard[2].indexOf(w[j]) > -1) {
              currentRow = 2
            }
          } else {
            if (keyboard[currentRow].indexOf(w[j]) === -1) {
              break
            } else if (keyboard[currentRow].indexOf(w[j] > -1 && j === w.length - 1){
              results.push(words[i]
            }
          }
        }
      }
      return results
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.