예제를 통한 JavaScript: Palindrome 순열(기능적)

"Javascript by Example"은 일반적인 코딩 인터뷰 및 LeetCode 스타일 문제와 일반 유틸리티를 구현하는 일련의 게시물입니다. 최소한의 우아한(그러나 여전히 학습하기 쉬운) 방식으로 구현하고 다양한 구현을 비교합니다.


고전적인 회문(문자열이 오른쪽에서 왼쪽으로 읽는 것과 왼쪽에서 오른쪽으로 같은 방식으로 읽는지 확인하는 경우에만 확인)과 달리 이 연습은 문자열의 순열이 회문인지 여부를 알아내는 것입니다.

예를 들어 단어가 회문이기 때문에 함수는 "racecar"라는 문자열에 대해 true를 반환해야 합니다. 그러나 순열 "aba"(회문)가 있기 때문에 문자열 "aab"에 대해서도 true를 반환해야 합니다.

이것을 짧고 (상대적으로) 기능적인 한 줄로 구현할 수 있는지 먼저 봅시다.

문제 이해

잠시 동안 회문에 대해 생각해 보면, 회문이 완전히 대칭이거나(문자열의 왼쪽 절반이 오른쪽 절반과 완전히 일치함) 중앙에 일치하지 않는 문자가 하나 있음을 알 수 있습니다("racecar"예에서처럼). .

따라서 일치하지 않는 문자를 추적하면 원하는 위치에 매우 가까워집니다.

우리는 고유한 문자 모음을 다루고 있으므로 Set을 데이터 구조로 사용하겠습니다. 따라서 문자열을 일치하지 않는 문자만 포함하는 집합으로 줄여 보겠습니다.

const palindromePerm = s => [...s].reduce(
  (xs, x) => (xs.delete(x) || xs.add(x), xs),
  new Set()
)

palindromePerm('carerac') // Set(1) { 'e' }
palindromePerm('abab') // Set(0) {}

무슨 일이 일어나고 있는지 명확하지 않은 경우 - 먼저 ES6+ 확산 구문을 사용하여 문자열을 배열로 바꿉니다. 그런 다음 값이 집합에 있으면 true를 반환하는 Set.delete() 메서드를 사용하여 일치하지 않는 문자만 포함하는 집합으로 배열을 줄입니다(그렇지 않으면 집합에 추가합니다).

그리고 이것은 우리를 첫 번째 작업 솔루션에 매우 가깝게 만듭니다. 위에서 언급한 두 가지 시나리오를 모두 다루기 위해 세트에 항목이 0개 또는 1개 있는지 확인하기만 하면 됩니다.

const palindromePerm = s => [...s].reduce(
  (xs, x) => (xs.delete(x) || xs.add(x), xs),
  new Set()
).size < 2

palindromePerm('carerac') //true
palindromePerm('word') //false

다음과 같이 시도하면 실패합니다.

palindromePerm('Race car') //false

그러나 대문자와 공백에 대한 지원을 쉽게 추가할 수 있습니다.

s.toLowerCase().replaceAll(' ', '')

또는 더 일반적으로 정규식을 사용하면 다음과 같습니다.

s.replace(/[^A-Za-z0-9]/g, '')

또한 새 게시물에 명령형 버전을 추가할 예정입니다.


참고: 여기서는 "기능적"이라는 용어를 상대적인 의미로 사용하고 있습니다. JS는 순전히 기능적 언어가 아니며 여기서 순전히 기능적이고 변경 불가능한 접근 방식을 사용하면 이러한 예제가 더 복잡해집니다.

이러한 유형의 게시물이 흥미롭다면 알려주세요(반응 및/또는 댓글 포함).