[Cracking The Coding Interview] 1.9: String Rotation

[jtkaufman737]

string rotation: assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring. (e.g., "waterbottle" is a rotation of "erbottlewat")

[jtkaufman737]

https://repl.it/@jtkaufman737/EmptyFumblingComputationalscience

function isRotation(str1, str2) {
  let start, stop;

  for(let i=0; i < str1.length; i++) {
    if(str1[i] !== str2[i]) {
      if(start == undefined) {
        start = i;
      } else if(str1[i + 1] === str2[i + 1]) {
        stop = i;
      }
    }
  }

  let unRotated = str2.substring(0, start) + str2.substring(start,stop + 1).split("").reverse().join("")+ str2.substring(stop + 1, str2.length);
  return unRotated === str1 ? "Success! Possible rotation" : "Failure! Not a possible rotation";
}

//isRotation("fish","ifsh") // yes 
//isRotation("fihs","fish") // yes
//isRotation("racecar","racerac") // yes but I'm not sure how(???) 
isRotation("racecar","foobar") // no 

/* Authors note: I realized using this method if during the "diff" (counting after they diverge) technically
it could get a false positive if the "rotated" string still had the same letter at [i] as the non 
rotated string did. I thought Racecar should break for that reason, but it didn't... This also wouldn't 
work if the rotated word was in the middle of an otherwise non rotated word (I would need multiple stops or an inner loop to deal with it.)

the other way I'd thought of doing this was splitting the word onto fragments where they diverged...that 
still may have been the better option 

*/

[lpatmo]

I looked at this really complicatedly, then realized the easiest solution is to add s1 to itself, then check if s2 is a substring of s1.

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

// string rotation: assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring. (e.g., "waterbottle" is a rotation of "erbottlewat")

//wwaterbottle //water
function isSubstring(s1,s2) {
  //check that s2 is a substring of s1
  //return true or false
  let indexes = [];
  let start = 0;
  while (s1.indexOf(s2[0], start) > -1) {
    indexes.push(s1.indexOf(s2[0], start));
    start = s1.indexOf(s2[0], start) + 1;
  }

  for (let i = 0; i < indexes.length; i++) {
    if (s1.substring(indexes[i], s2.length + indexes[i]) === s2) {
      return true;
    }
  }
  return false; 
}
//wwwaterbottle, waterbottle
console.log(isSubstring("waterbottle", "erbottlewat"))

function isRotation(s1, s2) {
  //check that everything in s1 is in s2
  if (s1.length !== s2.length) {
    return false;
  }
  return isSubstring(s1+s1, s2)
}

console.log(isRotation('waterbottle', 'erbottlewat'))//true