Anagram Finder

Posted: 08 December, 2018 Category: code Tagged: algorithms

I will preface this with I am bad at algorithms. Like, TERRIBAD. My having very little patience to read through explanations of time and space complexity without dropping packets / falling asleep / passing out might have something to do with this. Nevertheless:

An Anagram Finder. I just thought this was cute, OK?

I made a thing. And I made it without referring to anything. And for simple strings, it seems to work. But I'm mainly posting it here because, when you create something from scratch, and give things their cutesy lil variable names and function names, they are like a babe you've just delivered unto the world. You think it's great. You think the way the debugger steps through its simple lines, switching into this or that block under just the right circumstances, is adorable. You Gush. You squee with glee when the first characters are chomped off of the beginnings of the arrays, by the invisible pacman devouring things in stepwise slo-mo...

const isAnagram = (stringA, stringB) => {
  let lcStringA = stringA.toLowerCase();
  let lcStringB = stringB.toLowerCase();

  //not proud, looks redundant... but one cannot be an anagram of ones self, OK?
  if(lcStringA === lcStringB) {
    return false;
  }
  let arrA = lcStringA.split('');
  let arrB = lcStringB.split('');
  let arrLen = arrA.length;
  if(arrLen !== arrB.length) {
    return false;
  }
  if(arrLen === 0) {
    return false;
  }
  
  let remainingRotations = arrLen;
  do {
    // knockout the pairs
    if(arrA[0] === arrB[0]) {
      // drop pair
      arrA.shift();
      arrB.shift();
      arrLen -= 1;
      remainingRotations = arrLen;
    } else {
      // rotate A
      arrA.push(arrA.shift());
      remainingRotations -= 1;
    }
  } while (remainingRotations);
  return (arrA.length === 0); //if there's anything left, its not an anagram
}

Reality Check

OK I should prolly go look at how this is ACTUALLY done. Off the bat, google fessed up this link from geeksforgeeks.

Looking at the first solution, I'm quite chuffed actually, cos they pretty much do the same thing! Egads... haven't seen C++ code in a while... it looks way more torturous to convert the strings into character arrays: I had one-liner es6 .split() magic on my side. There's also sorting going on. Now I don't explicitly sort anything... but if I'm implicitly sorting (as I suspect) and am just too silly to realize this, well... fine: give me my L sign. Now can we just both get on with our lives.

The second solution relying on 8-bit chars is interesting. Not enough for me to parse though. Let's look for other impl's: Found this standford pdf. It does mention the obvious brute force approach off the bat. Funnily enough, this did not occur to me. I wish it had, then I could gloat: "Well, I didn't do it the naive way because it's like, you know, SOOO inefficient dahlink" but I... genuinely... didn't think of it o.O Nice to know the brute force way is horibbly inefficient - O(n!) !!

They discuss the other solutions too, which... Sorry... wait...

I'm having a nosebleed.