Question 316763 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Which code is better? Efficiency vs code readability

I solved a problem using different approaches. I was wondering which approach is better.

I believe in terms of time complexity, the first approach is more efficient, but the code is long and looks very messy, but it uses 1 less for loop.
The second approach uses 3 for loops, but the code looks much cleaner.
I wanted to ask you which code you believe is better, as whether we should prioritise an efficient but messy code, or a less efficient but easier to read code.

This is the problem statement:

Given an array of strings words, return the words that can be typed using letters of the alphabet on only one row of American keyboard like the image below.

In the American keyboard:

the first row consists of the characters "qwertyuiop",
the second row consists of the characters "asdfghjkl", and
the third row consists of the characters "zxcvbnm".

First Approach (Messy but efficient):

var findWords = function(words) {
    const first_row = "qwertyuiop";
    const second_row = "asdfghjkl";
    const third_row = "zxcvbnm";
    let row = "first";
    let accepted_words = [];

    words.forEach((word) => {
        for (var i = 0; i < word.length; i++) {
            if (i === 0) {
                if (first_row.includes(word[i].toLowerCase())) {
                    if (i === word.length - 1) accepted_words.push(word);
                    row = "first";
                } else if (second_row.includes(word[i].toLowerCase())) {
                    if (i === word.length - 1) accepted_words.push(word);
                    row = "second";
                } else if (third_row.includes(word[i].toLowerCase())) {
                    if (i === word.length - 1) accepted_words.push(word);
                    row = "third";
                } else {
                    break;
                }
            } else {
                if (first_row.includes(word[i].toLowerCase()) && row === "first") {
                    if (i === word.length - 1) accepted_words.push(word);
                } else if (second_row.includes(word[i].toLowerCase()) && row === "second") {
                    if (i === word.length - 1) accepted_words.push(word);
                } else if (third_row.includes(word[i].toLowerCase()) && row === "third") {
                    if (i === word.length - 1) accepted_words.push(word);
                } else {
                    break
                }
            }
        }
    });

    return accepted_words;
}

Second Approach (less efficient):

var findWords = function(words) {
    const rows = ["qwertyuiop", "asdfghjkl", "zxcvbnm"];
    let accepted_words = [];

    words.forEach((word) => {
        for (row of rows) {
            for (var i = 0; i < word.length; i++) {
                if (row.includes(word[i].toLowerCase())) {
                        if (i === word.length - 1) {
                            accepted_words.push(word);
                        }
                } else {
                    break
                }
            }
        }
    });

    return accepted_words;
}
Tags:

2

Answers


  1. 0

    Your first snippet actually is not more efficient. Sure, it has one for less, but instead it has 6 ifs. It’s just unrolling the loop, which is possible as it is looping over a fixed-size array. It has constant complexity (O(1)) in both solutions.

    To actually make this faster, skip looking at the other rows after having accepted a word, and use some higher-order functions to make it more readable:

    const rows = ["qwertyuiop", "asdfghjkl", "zxcvbnm"];
function findWords(words) {
    return words.filter(word => {
        return rows.some(row => {
            return word.split('').every(letter => {
                return row.includes(letter.toLowerCase());
            });
        });
    });
}

    To make it faster even for huge alphabets (not just 26 English letters) and for equally enormous keyboards (with lots of large rows not just just 3), avoid looping over the rows and looping over the letters in that row (with includes). Pre-process the keyboard layout into a lookup map:

    const rows = ["qwertyuiop", "asdfghjkl", "zxcvbnm"];
const rowByLetter = new Map(rows.flatMap(row =>
    row.split('').map(letter => [letter, row])
));
function findWords(words) {
    return words.filter(word => {
        if (word.length <= 1) return true;
        const row = rowByLetter.get(word[0].toLowerCase());
        return word.slice(1).split('').every(letter =>
            row === rowByLetter.get(letter.toLowerCase())
        );
    });
}
    Login or Signup to reply.
  2. 0

    You can do it in 2 loops if you don’t mind doing some of the work first – in this case creating an object that links each letter with the row it appears in. Then you can use that object as a quick O(1) reference when it’s time to analyze some words.

    const rows = ["qwertyuiop", "asdfghjkl", "zxcvbnm"];

const rowLookup = rows.reduce((look, row, rowindex) => {
  row.split("").forEach((letter) => {
    look[letter] = rowindex;
  });
  return look;
}, {});

//console.log(rowLookup);

var findWords = function(words) {
  return words.filter(word => {
    let [firstLetter, ...letters] = word.toLowerCase().split("");
    return letters.every(l => rowLookup[l] === rowLookup[firstLetter]);
  });
};

let x = "This is a typewriter".split(" ");

console.log(findWords(x));
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search