Algorithm - All about palindrome

April 12th 2019

Palindrome이란 단어를 뒤집어도 동일한 단어가 되는 단어를 말합니다. 알고리즘 문제를 풀다보면 자주 접하게 되어 정리를 한 번 해보려고 합니다.

먼저 심플하게 함수를 구현해 보면 아래와 같이 array method를 사용할 수 있습니다.

function palidrome(str) {
  return (
    str ===
    str
      .split('')
      .reverse()
      .join('')
  );
}

reverse method 또는 array method를 사용하지 않고 for 문으로는 아래와 같이 구현할 수 있습니다.

function palindrome(str) {
  let reversedStr = '';

  for (let i = 0; i < str.length; i++) {
    reversedStr = str[i] + reversedStr;
  }

  return str === reversedStr;
}

// or

function palindrome(str) {
  let reversedStr = '';

  for (let i = str.length - 1; i >= 0; i--) {
    reversedStr += str[i];
  }

  return str === reversedStr;
}

위와 같이 가장 직접적인 방법으로 문제를 풀 수 있습니다. 또 다른 방법으로도 접근할 수 있는데 every method를 활용해서 풀 수 있습니다.

function palindrome(str) {
  return str
    .split('')
    .reverse()
    .every((char, idx) => char === str[i]);
}

// or
function palindrome(str) {
  return str.split('').every((char, idx) => char === str[str.length - 1 - idx]);
}

위의 기본 풀이 방법을 인지하고, codewars에서 palindrome 관련 문제를 몇 개 풀어보고자 합니다.

문제 ) Palindrome for your Dome

A palindrome is a word, phrase, number, or other sequence of symbols or elements, whose meaning may be interpreted the same way in either forward or reverse direction. Famous examples include "Amore, Roma", "A man, a plan, a canal: Panama" and "No 'x' in 'Nixon'". - wikipedia

Our goal is to determine whether or not a given string is a valid palindrome or not.

Like the above examples, here are a few test cases which are also populated:

"Amore, Roma" => valid
"A man, a plan, a canal: Panama" => valid
"No 'x' in 'Nixon'" => valid
"Abba Zabba, you're my only friend" => invalid

You can see that they are case insensitive and disregards non alphanumeric characters. In addition to a few predefined tests, your function will also be tested against a random string generator 50 times which are guaranteed to produce valid palindromes.

Notes:

reverse/reverse! have been disabled for String/Array and reverse() for JS. reverse cannot get used in Haskell either the empty string "" can be read forward or backward the same, it's a palindrome in our case.

문제를 보면, reverse를 사용할 수 없고 특수 문자를 제외해야 하는 것 외에는 위에서 풀어 보았던 palindrome과 동일합니다.

argument로 주어진 string을 반대로 돌릴 후 본래의 string과 비교한 boolean 값을 반환하는 동일한 작업입니다.

function palindrome(string) {
  string = string.toLowerCase();

  let str = '';
  let reversedStr = '';

  for (let i = 0; i < string.length; i++) {
    const charCode = string[i].charCodeAt();

    if (charCode >= 97 && charCode <= 122) {
      str += string[i];
      reversedStr = string[i] + reversedStr;
    }
  }

  return str === reversedStr;
}

정규표현식을 적절히 사용하면 조금 더 간략하게 코드를 짤 수 있을 거 같습니다.

function palindrome(string) {
  string = string.toLowerCase().replace(/[^a-z]/g, '');

  return string.split('').every((char, idx) => char === string[string.length - 1 - idx]);
}

위에서 every를 사용했는데, reduce method로도 구현이 가능합니다.

function palindrome(string) {
  string = string.toLowerCase().replace(/[^a-z]/g, '');

  return string === string.split('').reduce((acc, char) => char + acc);
}

// or
function palindrome(string) {
  string = string.toLowerCase().replace(/[^a-z]/g, '');

  return string === string.split('').reduceRight((acc, char) => acc + char);
}

Handmade with .