1.2 Check Permutation

[rmorabia]

Given two strings, write a method to decide if one is a permutation of the other.

[rmorabia]

https://repl.it/@rmorabia/IdealAshamedOutcomes

// CTCI 1.2
// this is definitely cheating

function perm(string1, string2) {
  string1 = string1.split('').sort()
  string1 = string1.toString()
  string2 = string2.split('').sort()
  string2 = string2.toString()
  
  if (string1 === string2) {
    console.log("Because isn't the first cardinal rule of perm maintenance that you're forbidden to wet your hair for at least 24 hours after getting a perm at the risk of deactivating the immonium thygocolate?")
  } else {
    console.log("What? Like it's hard?")
  }
}

perm('abc', 'bca')

[megantaylor]

https://repl.it/@megantaylor/CheckPermutation

function checkPermutation(str1, str2) {
  if(str1.length !== str2.length) return false;
  let sortedStr1 = [...str1].sort().join("");
  let sortedStr2 = [...str2].sort().join("");
  return sortedStr1 === sortedStr2;
}

[lpatmo]

https://repl.it/@lpatmo/TurboKnowingDictionary

The first solution was the easiest. Then decided to try to compare objects. Then @ISPOL had crazy idea of using recursion.

//Given two strings, write a method to decide if one is a permutation of the other.

/** SOLUTION 1: slower solution, relying on sort */
//Same length. If not, return false.
//Sort each string, then compare if equal

function isPermutation1(str1, str2) {
   if (str1.length !== str2.length) {
     return false;
   }
   str1Sorted = str1.split("").sort().join("");
   str2Sorted = str2.split("").sort().join("");
   return str1Sorted === str2Sorted;
}

console.log(isPermutation1("abb", "aab"))
//Big O: 1 + n + nlogn + n ==> nlogn
//Space complexity: O(n) (Think: splitting up the string. Sort is irrelevant.)

/** SOLUTION 2: solution */
//Same length. If not, return false.
//Create a holder object containing all chars and counts for str1. Then create a similar holder object for str2.
//Compare the two objects and check if equal.

function isPermutation2(str1, str2) {
   if (str1.length !== str2.length) {
     return false;
   }
   let obj1 = {};
   let obj2 = {};
   for (let i = 0; i < str1.length; i++) {
     if (obj1[str1[i]]) {
       obj1[str1[i]] += 1;
     } else {
       obj1[str1[i]] = 1;
     }
   }
    for (let i = 0; i < str2.length; i++) {
     if (obj2[str2[i]]) {
       obj2[str2[i]] += 1;
     } else {
       obj2[str2[i]] = 1;
     }
   }
   //console.log(obj1)
   //console.log(obj2)
   //Check if our two objects are equal!
   //First: do they have the same number of properties?
   let obj1Props = Object.getOwnPropertyNames(obj1)
   let obj2Props = Object.getOwnPropertyNames(obj2)
   if (obj1Props.length !== obj2Props.length) {
     return false;
   }
   //Next: check that the values between objs are equal
   for (let i = 0; i < obj1Props.length; i++) {
     if (obj1[obj1Props[i]] !== obj2[obj1Props[i]]) {
       return false;
     }
   }
   //EASIER: or could use JSON.stringify to compare object equality:
   //return JSON.stringify(obj1) === JSON.stringify(obj2)
  return true;
}

console.log(isPermutation2("abb", "aab"))
//Big O: O(n)
//Space complexity: O(n)

/*** RECURSIVE SOLUTION ***/
//Take first letter. Check if this letter is in second string. If found, do again, but with the letter removed from both strings. (Recursion.) If not found, return false.

function isPermutation3(str1, str2) {
  if (str1.length !== str2.length) {
    return false;
  }
  if (str1.length === 0 && str2.length === 0) {
    return true;
  } 
  let first = str1[0];
  let foundIndex = str2.indexOf(first);
  if (str2.indexOf(first) > -1) {
    return isPermutation3(str1.slice(1), str2.slice(0, foundIndex) + str2.slice(foundIndex+1))
  } else {
    return false;
  }
}
console.log(isPermutation3("abb", "aab"))
//Big O: O(n)
//Space complexity: O(1)?

[mcsmithers]

Christina's solution

function getPermutations(myStr) {
  const firstPermutationResults = [];

  if (myStr.length === 1) {
    firstPermutationResults.push(myStr);
    return firstPermutationResults;
  }

  for (let char = 0; char < myStr.length; char++) {
    // so we're first forming the words with a starting point and then recursively building
    const firstLetter = myStr[char];
    const otherLetter = myStr.substring(0, char) + myStr.substring(char + 1);
    const otherPermutations = getPermutations(otherLetter);

    for (let anotherChar = 0; anotherChar < otherPermutations.length; anotherChar++) {
      firstPermutationResults.push(firstLetter + otherPermutations[anotherChar]);
    }

  }
  return firstPermutationResults;
}

const permutation = getPermutations('dog');
console.log(permutation);

// Time to compare
const otherStr = 'god';

const iterator = permutation.values();

// Yay, some es 6
for (const value of iterator) {
  if (otherStr == value) {
    console.log('Match! "' + value + '" is the same as "' + otherStr + '"');
  }
  else {
    console.log(otherStr + ' is not a match for ' + value);
  }
}