5
\$\begingroup\$

I came across this question which asks to create a function which will return true/false based on the passed array containing all the letters to make up the passed word. Each letter from array can only be used once.

Here's my attempt:

const checkArray = (word, arr) => {
    let good = true
    word.split('').forEach(letter => {
        const letterIdx = arr.findIndex(arrLetter => arrLetter === letter)
        if (letterIdx === -1) good = false

        arr.splice(letterIdx, 1)
    })

    return good
}

const word = 'goal'
const arr1 = ['g', 'o','a','l','x','a','d'] // true
const arr1 = ['g', 'r','a','l','x','a','d'] // false

With my approach, a loop inside a loop is used. What's a better (less complexity) way of solving this issue?

\$\endgroup\$
0

2 Answers 2

Reset to default
8
\$\begingroup\$

appropriate names

const checkArray = (word, arr) => {

This is just a terrible signature, almost as meaningless as const foo = (bar, baz) ....

Tell the caller what's going to happen:

const checkWordMatchesLetters = (word, letters) => {

and then explain to the caller that we expect a vector of letters.

early exit

        if (letterIdx === -1) good = false

There's no need to keep going after we encounter a missing letter.

This could just be return false. In fact, there's no need for a good flag, given that control flow within our function suffices.

@ggorlen helpfully points out that literally using that return

unfortunately just breaks out of that iteration of the forEach callback, and the return value is ignored. Really, forEach is inappropriate here -- .every or for .. of would allow early exit.

Indeed, quite right. I was essentially looking for an all() helper here.

appropriate datastructure

        arr.splice(letterIdx, 1)

The .findIndex() call had linear \$O(n)\$ time complexity cost, and asking .splice() to shift elements to shrink the array has similar cost. So operating on a word of modest length like "supercalifragilisticexpialidocious" would entail hundreds of operations, where surely only a couple dozen should suffice. In total we have quadratic \$O(n^2)\$ cost.

Consider implementing a multiset (counter) via an object mapping, from letter to count. Linear cost to construct it, and constant cost to verify each positive count while decrementing each given letter's count, adding up to a total of linear cost.

Even if you don't go that far, we could have a better (still quadratic) algorithm by writing a tombstone sentinel into an array of letters, to show we have "used up" that particular letter. Probably better to operate on a copy of caller's parameter, so caller isn't surprised we trashed his array. Going a bit further, if you invest \$O(n \log n)\$ effort in sorting that copied array, you can enjoy \$O(\log n)\$ lookup times via binary search.

\$\endgroup\$
0
3
\$\begingroup\$

Single Responsibility Principle reduces complexity

The word - function input - is cleaned of duplicate letters beforehand, allowing for a much simplified and clear "contains" function - uniqueLetters.every

const wordInAlphabet = (word, alphabet) => {
    let uniqueLetters = [...new Set(word)]
    return uniqueLetters.every(char => alphabet.includes(char))
}

StackOverflow References:

\$\endgroup\$
4
  • 2
    \$\begingroup\$ It's not clear from the problem statement that duplicates should be removed (we're missing a test case such as "noon", "nno"). So perhaps we need to use multiset instead. \$\endgroup\$ Commented Mar 29, 2024 at 10:03
  • \$\begingroup\$ @TobySpeight, I agree that multiset (counter) is a requirement. I feel the problem statement was pretty clear: "Each letter from array can only be used once." I would definitely expect a thumbsdown result from ("noon", "nno"). If we think about the Business Domain for this problem, it seems a fair match for manipulating Scrabble tiles. \$\endgroup\$ Commented Mar 29, 2024 at 16:35
  • \$\begingroup\$ Yeah the idea is that duplicates are allowed but a letter is only allowed to be used once. So if the target is "grill", then [g, r, i, l] is a fail whereas [g, r, i, l, l, l] is ok \$\endgroup\$ Commented Mar 29, 2024 at 20:25
  • \$\begingroup\$ Problem statements are tricky. You go with what you got. My code example meets the problem statement. It tests if the alphabet-array contains the word's letters. Each letter from array can only be used once. So eliminating word-letter-duplicates meets the constraint. As for complexity - the threads theme - applied OO guidelines keeps complexity under control. If there is a larger real-world concept that may infer other requirements, well, it is not in this problem statement. It's all guesswork. \$\endgroup\$ Commented Mar 29, 2024 at 21:08

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.