796. Rotate String

💡 풀이

var rotateString = function (A, B) {
  if (A === B) return true;

  for (let char of A) {
    A = A.slice(1) + A.slice(0, 1);
    if (A === B) return true;
  }
  return false;
};
let s = 'bbbacddceeb',
  goal = 'ceebbbbacdd';

rotateString(s, goal);

📝 정리

String 관련해서 간단한 문제다. slice 함수를 이용해서 반복문을 돌때마다 rotate를 시켜주고, 두 string이 같은 순간이 오면 true를 return 해주면 된다.

간단한 풀이보다는 String matching 관련 문제에서는 두 알고리즘을 기억하고 있어야 한다. 가장 기본적인, 즉 Naive한 String matching 알고리즘을 사용한다면 매번 문자열을 비교할 때마다 얻게되는 정보를 다음 번 문자열 비교에서 사용하지 않고 계속 새로 비교하게 된다. 이러한 비효율성을 극복하기 위해 KMP, Rabin-Carp 등의 매칭 알고리즘을 사용한다.

• 알고리즘 자체를 외운다기보다 두 알고리즘을 사용했을 때 시간 복잡도 O(N)으로 matching을 할 수 있다는 점을 기억하고 있어야 함)

• 두 알고리즘에 관한 설명은 inJae, Covenant님 블로그에 자세히 설명되어 있기 때문에 링크를 남겨놓겠습니다!

• KMP 알고리즘

• Rabin-Carp 알고리즘

수정, 지적을 환영합니다!

문제 링크

https://leetcode.com/problems/rotate-string/

LeetCode GitHub

https://github.com/tTab1204/LeetCode