JavaScriptのPalindrome(回文)問題の解き方と注意点

Palindromeとは

Palindromeとは「回文」という意味。

上から読んでも下から読んでも同じになる文を回文と言います。

例えば「しんぶんし」や「level」はどちらから読んでも同じなので回文です。

回文の問題はFizz Buzzくらいよく見かける問題なので、もしエンジニア採用などでPalindromeを知らないと評価が下がるので注意が必要です。

文字列が回文か判定する方法

JavaScriptでは文字列を直接逆にするメソッドが存在しません。

そのため文字列をいったん配列にしてからreverse()で逆順にしてjoin('')で文字列で戻すのが定石となっています。

const str1 = 'label'
const result1 = str1.split('').reverse().join('')
console.log(result1)
// => 'lebal'

const str2 = 'level'
const result2 = str2.split('').reverse().join('')
console.log(result2)
// => 'level'

文字列が回文か判定するには以下のように書きます。

const isPalindrome = (x) => {
  const currentText = x
  const palindromeText = currentText.split('').reverse().join('')
  return  currentText === palindromeText
}
console.log(isPalindrome('label'))
// => false

console.log(isPalindrome('level'))
// => true

LeetCodeの回文問題を解いてみる

前述の処理が理解できたら次にLeetCodeというサイトの問9と問125を解いてみてください。

応用問題になりますが、JavaScriptの基礎が理解できていれば解けるはずです。

9. Palindrome Number

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward.

For example, 121 is a palindrome while 123 is not.

Example 1:
Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:
Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:
Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
 
Constraints:
-231 <= x <= 231 - 1
const isPalindrome = (x) => {

}

125. Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:
Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.
 
Constraints:
1 <= s.length <= 2 * 105
s consists only of printable ASCII characters.
const isPalindrome = (s) => {

}

LeetCode 問9の答え

引数で受け取るのが数値なのでString()で文字列に変換してから処理する。

const isPalindrome = (x) => {
  const currentText = String(x)
  const palindromeText = currentText.split('').reverse().join('')
  return  currentText === palindromeText
}
console.log(isPalindrome(121))
// => true

console.log(isPalindrome(-121))
// => false

console.log(isPalindrome(10))
// => false

LeetCode 問125の答え

英語は大文字が含まれるのでtoLowerCase()で小文字に変換。

使用するのはアルファベットと数字だけなのでそれ以外は除去した文字列をreplace()を使って作り、これを元に回文を作って比較します。

「Alphanumeric characters include letters and numbers.」という条件があるので、数字が含まれることも考慮されていなければ間違いです。

const isPalindrome = (s) => {
  const replacedText = s.toLowerCase().replace(/[^a-z0-9]/g, '')
  const palindromeText = replacedText.split('').reverse().join('')
  return replacedText === palindromeText
}
console.log(isPalindrome('A man, a plan, a canal: Panama'))
// => true

console.log(isPalindrome('race a car'))
// => false

console.log(isPalindrome(' '))
// => true

おまけ

最近「回文21面相」という回文投稿サイトに公開された回文がすごかったのでご紹介。

だんだん敗退でプーチン成果少ない。生命軽視し畏敬・名声失くす開戦、チープで痛い判断だ。
(だんだんはいたいでぷーちんせいかすくないせいめいけいししいけいめいせいなくすかいせんちーぷでいたいはんだんだ)

https://kaibun.jp/works/71718/
だんだん敗退でプーチン成果少ない。生命軽視し畏敬・名声失くす開戦、チープで痛い判断だ。

回文か判定するJavaScriptで確認するとtrueになるので回文になっていることがわかる。

const isPalindrome = (s) => {
  const palindromeText = s.split('').reverse().join('')
  return s === palindromeText
}
const kaibun = 'だんだんはいたいでぷーちんせいかすくないせいめいけいししいけいめいせいなくすかいせんちーぷでいたいはんだんだ'
console.log(isPalindrome(kaibun))
// => true