1
\$\begingroup\$

I am writing a program in JavaScript to find all possible words given 7 letters. The words have to be 3 or more characters, and for right now I am limiting it to 7 characters long. The code below works, but takes forever to complete and I would like to speed it up. Would recursion help?

Thanks for any suggestions.

The variable wordList is an array of 60,000 words.

    function isWord(word){
        var found = wordList.indexOf(word);
        if(wordList[found]===word) return true;
            else return false;
    }
    for(var i=0; i<letters.length; i++) {
        for(var j=0; j<letters.length; j++) {
            for(var k=0;k<letters.length; k++) {
                if(isWord(letters[i]+letters[j]+letters[k]))
                    w.push(letters[i]+letters[j]+letters[k])
            }
        }
    }
    for(var i=0; i<letters.length; i++) {
        for(var j=0; j<letters.length; j++) {
            for(var k=0; k<letters.length; k++) {
                for(var l=0; l<letters.length; l++) {
                    if(isWord(letters[i]+letters[j]+letters[k]+letters[l]))
                    w.push(letters[i]+letters[j]+letters[k]+letters[l])
                }
            }
        }
    }
    for(var i=0; i<letters.length; i++) {
        for(var j=0; j<letters.length; j++) {
            for(var k=0; k<letters.length; k++) {
                for(var l=0; l<letters.length; l++) {
                    for(var m=0; m<letters.length; m++) {
                        if(isWord(letters[i]+letters[j]+letters[k]+letters[l]+letters[m]))
                        w.push(letters[i]+letters[j]+letters[k]+letters[l]+letters[m])
                    }
                }
            }
        }
    }
    for(var i=0; i<letters.length; i++) {
        for(var j=0; j<letters.length; j++) {
            for(var k=0; k<letters.length; k++) {
                for(var l=0; l<letters.length; l++) {
                    for(var m=0; m<letters.length; m++) {
                        for(var n=0; n<letters.length; n++) {
                            if(isWord(letters[i]+letters[j]+letters[k]+letters[l]+letters[m]+letters[n]))
                            w.push(letters[i]+letters[j]+letters[k]+letters[l]+letters[m]+letters[n])
                        }
                    }
                }
            }
        }
    }
    for(var i=0; i<letters.length; i++) {
        for(var j=0; j<letters.length; j++) {
            for(var k=0; k<letters.length; k++) {
                for(var l=0; l<letters.length; l++) {
                    for(var m=0; m<letters.length; m++) {
                        for(var n=0; n<letters.length; n++) {
                            for(var o=0; o<letters.length; o++) {
                                if(isWord(letters[i]+letters[j]+letters[k]+letters[l]+letters[m]+letters[n]+letters[o]))
                            w.push(letters[i]+letters[j]+letters[k]+letters[l]+letters[m]+letters[n]+letters[o])
                            }
                        }
                    }
                }
            }
        }
    }
\$\endgroup\$
2
\$\begingroup\$

You are forming each possible combination, and look for it in the dictionary. That indeed takes forever. You'd be in a better shape doing it other way around. Read the dictionary word by word, and for each word check if it is composed by your letters. In pseudocode,

    for letter in word
        if letter not in letters
            return false
    return true
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Yes, recursion would certainly be a better solution. That would look something like:

function checkForWords(input) {
  let words = [];

  function recurseLetters(letters, currentString) {
    if (currentString.length >= 3 && isWord(currentString)
      wors.push(currentString);
    letters.forEach( (letter, i) => {
      recurseLetters(letters.slice().splice(i,1),, currentString + letter;
    });
  }

  recurseLetters(input.split(''), '');        
}

However this doesn't check for duplicate words (say your input is aelpp) and probably won't perform much better.

To speed up isWord there are two options. Either use the includes built in:

function isWord(word){
    return wordList.includes(word);
}

another option is to build a hash and use that. This would work well if you are making multiple calls to offset the once off expense of building the hash.

let wordHash = {};
wordList.forEach( (word) => { wordHash[word]=true } );
function isWord(word){
    return wordHash[word];
}

in general you would need to measure the performance of each alternative.

Another way of solving this problem usually involves sorting the letters in each dictionary word and in the input. This requires a bit more planning but usually means testing fewer permutations.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.