Create a function that accepts an array of words as it's input

Question

Seen this whiteboard challenge online and can't seem to figure it out. HELP!

Create a function that accepts an array of words as it's input.

Your function should return an array of all words that can be typed using letters of the alphabet that are only accessible on a single row of the standard American QWERTY keyboard.

For example:

// given
let words = [ 'sup', 'dad', 'tree', 'snake', 'pet'];
keyboardWords(words);

// return
['dad', 'tree', 'pet'];

And this is how far I've gotten.

const topKeys = ['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'];
const middleKeys = ['a', 's', 'd','f', 'g', 'h', 'j', 'k', 'l'];
const buttomKeys = ['z', 'x', 'c', 'v', 'b', 'n', 'm'];

let result = [];

let words = ['sup', 'dad', 'tree', 'snake', 'pet'];

for(let i in words) {
  let eachWord = words[i];

  eachWord.split('').forEach(function(c) {
    console.log(c);
  });

}

I've got to the point where I'm printing each word in the array but dont completly know what method to use to see if each letter in the words in a single array thats topKeys, middle Keys etc...

Ullrich

What word can you make out of: const buttomKeys = ['z', 'x', 'c', 'v', 'b', 'n', 'm']; ? There's no vowels. – Misology

Answer 1

See Array.prototype.filter(), Set, Spread Syntax, String.prototype.toLowerCase(), and Array.prototype.every() for more info.

// Input.
const input = [
  'ERUT', // top match
  'wdvrmg', // false
  'dsjf', // middle match
  '!^#@&^#', // false
  'CxmvN', // bottom match
  '53454', // false
  '' // false
]

// Match.
const match = (A, B) => [...A].every(x => B.has(x.toLowerCase()))

// Line Words.
const lineWords = words => words.filter(word => word.length && (
  
  // Top match.
  match(word, new Set(['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'])) ||
  
  // Middle match.
  match(word, new Set(['a', 's', 'd','f', 'g', 'h', 'j', 'k', 'l'])) ||
  
  // Bottom match.
  match(word, new Set(['z', 'x', 'c', 'v', 'b', 'n', 'm']))
  
))

// Output.
const output = lineWords(input)

// Proof.
console.log(output)

Day

Why a Set and not just a plain array? – Katabolism

Because Set.has() is sublinear whereas Array.includes() within Array.every() adds unnecessary time complexity @Katabolism – Day

Answer 2

Obviously a lot of ways to do this. My initial reaction would be to make a hash table. I'm not sure it's better than any of the others, but it should perform reasonably and be easy to understand/write on a white board:

const rows = [
  ['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'],
  ['a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'],
  ['z', 'x', 'c', 'v', 'b', 'n', 'm']
];

// make a quick hash
const hash = rows.reduce((acc, row, i) => (row.forEach(letter => acc[letter] = i + 1), acc), {})
let words = ['sup', 'dad', 'tree', 'snake', 'pet', "4545", "", "PoWer", '0'];

let result = []

words.forEach(word => {
  if (!word) return                     // degenerate cases i.e  '', 0, etc.
  let row = hash[word[0].toLowerCase()]
  if (row == undefined) return          // not letters we know about
  for (let i = 1; i < word.length; i++) {
    if (hash[word[i].toLowerCase()] !== row) return
  }
  result.push(word)
})

console.log(result)

Tieback

Set is a hash table – Day

@ArmanCharan I understand that sets use hash tables, but they aren't the same thing. This depends on a single lookup resolving to a value that is then used to test against. As such it avoids potentially doing three look-ups for each letter. I think yours is fine, but this is a different idea. – Tieback

Answer 3

You should probably use .filter to check for which elements of an array pass a particular test. Then use every to see which words pass:

const keyboardWords = (() => {
  const topKeys = ['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'];
  const middleKeys = ['a', 's', 'd','f', 'g', 'h', 'j', 'k', 'l'];
  const bottomKeys = ['z', 'x', 'c', 'v', 'b', 'n', 'm'];
  return (words) => {
    return words.filter((word) => {
      const chars = word.split('');
      return chars.every(char => topKeys.includes(char))
        || chars.every(char => middleKeys.includes(char))
        || chars.every(char => bottomKeys.includes(char))
    });
  };
})();

const input = [ 'sup', 'dad', 'tree', 'snake', 'pet'];
console.log(keyboardWords(input))

Katabolism

Answer 4

One of many ways you can handle it:

const topKeys = ['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'];
const middleKeys = ['a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'];
const bottomKeys = ['z', 'x', 'c', 'v', 'b', 'n', 'm'];

const keysets = [topKeys, middleKeys, bottomKeys];

function fn(words) {
	let result = [];

	for (let j = 0; j < words.length; j++) {
		let word = words[j];
		keysets.forEach(function (keyset) {
			if (test(word, keyset)) {
				result.push(word);
			}
		});
	}

	function test(word, keyset) {
		let ok = false;
		for (let i = 0; i < word.length; i++) {
			let char = word.charAt(i);
			ok = keyset.indexOf(char) > -1;
			if (!ok) {
				break;
			}
		}

		return ok;
	}

	return result;
}

let words = ['sup', 'dad', 'tree', 'snake', 'pet'];

let result = fn(words);

console.log(result);

Bezel