6
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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`.
    
\$\endgroup\$
  • \$\begingroup\$ I should have added the proper comments to the code but somehow missed. isSameLength donates that the word & jumbledLetters are same in length. The duplicates are handled. Here is the jsbin \$\endgroup\$ – Jaganathan Bantheswaran Dec 28 '14 at 4:26
5
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Sorting both strings and checking for equals is an excellent approach. \$\endgroup\$ – Simon Forsberg Dec 27 '14 at 12:53
  • \$\begingroup\$ Nice one. But what happens if i have the word & jumbledLetters with different length. here is jsbin \$\endgroup\$ – Jaganathan Bantheswaran Dec 28 '14 at 4:29
  • \$\begingroup\$ Hmm, I agree for that you might be better of using the 2nd approach explained by thepace, which runs even faster. Where you use a hashmap with as key the letters in the alphabet. And you increase the values for each occurence in the word. Then you once run through the scrambled word and substract each value by one for the occurence, if at the end all values are <=0 they are a match. \$\endgroup\$ – DJanssens Dec 28 '14 at 12:18
1
\$\begingroup\$

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.

\$\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.