Finding the given word from jumbled letters

Question

I have tried to write JavaScript code to check whether I can form a word from the given string (jumbled):

function findWord(word, jumbledLetters, isSameLength) {
if(isSameLength && word.length !== jumbledLetters.length)
return false;

var uniquePosition = {};
for(var i = 0; i< word.length; i++)
for(var j=0; j< jumbledLetters.length; j++){
  if(word[i] === jumbledLetters[j] && j !== uniquePosition[j]) {
    uniquePosition[j] = j;
    break;
  }
}
return Object.keys(uniquePosition).length === (word.length);
}

I could do this with string permutation with minor changes, but I tried something like the above one. Could you please suggest refactoring to be done for the above code?

Answer 1

Yours is an \$O(n^2)\$ solution with extra space. Here are some solutions you could try:

• Sort both the arrays (\$O(n \log n)\$) and do a linear traversal (\$O(n)\$)index by index, wherever word[i]!=jumbledLetters[i], you have a mismatch.

• Use an array which maps the number of occurrence of each letter in the array. Traverse word and record the number of occurrences of the characters say,

  • For "potato", it would be a=1 b=0 c=0.....o=2,p=1 q=0...t=1...z=0 - \$O(n)\$.
  • Traverse jumbled letters and subtract each occurrence of the letter from the array. - \$O(n)\$)
  • We return false if we see the array index is 0 when we have an occurrence for that character.

Considering your code, here's a few input:

• isSameLength (what does it denote)? Either add comments or exclude it to the caller function where you are computing this variable.
• Formatting. It makes the code readable with no extra effort on the eyes.

• Are you handling duplicates i.e if a character is repeated in a word.

  // Consider the word to be aba and jumbled letters baa
  if(word[i] === jumbledLetters[j] && j !== uniquePosition[j])
      uniquePosition[j] = j; // here the letter's position gets overwrited.
  // Check your code if word = `aab` and jumbled = `bab`.
  

Answer 2

Your code is hard to read, please use correct indentation and brackets.

For example your for loop:

for(var i = 0; i< word.length; i++)

confused me at the start! Code shouldn't be confusing! Use brackets ;)

I believe the code will work (hypothetically), perhaps add some comments to make it a bit more clearer.
However your solution has a complexity of \$O(n²)\$, I would suggest to improve it.

A simple possible solution is to sort both strings alphabetically and run over them linear, this way you don't need to check if they are both of equal length, there is no need for 2 nested loops and it will run in linear time (sorting not included).

Example:

word: 'potato'
jumbled: 'otpato'

sorted word: 'aooptt'
sorted jumbled: 'aooptt'

run with one for loop over it and check if both match.

Goodluck!

Answer 3

I am going to mostly focus on style here.

1. You need to indent your code. According to JSLint, JavaScript should use 4-space indentation.

2. You need to use braces around all your ifs, fors, &c. According to JSLint, you should style your braces like this:

   function myFunction() {
   
       if (condition) {
           // Do something...
       }
   
       while (condition) {
           // Do something...
       }
   }
   

3. As demonstrated in the example above, you should also use a space after your closing parenthesis ) and your opening brace {.

4. The man who wrote JSLint has a list of good styles, which seems to be widely used by the JavaScript community.