Palindrome Check (回文チェック) アルゴリズム

文字列stringを受け取って、回文かどうかをチェックする。すべての文字を比較しないといけないので、どうやっても計算量が$O(n)$以上になるはず。

アルゴリズム実装(1) $O(n)$

両端から文字が等しいか比較していく:

function isPalindrome(string) {
    let left = 0
    let right = string.length - 1
    let result = true
    while (left <= right) {
        if (string[left] === string[right]) {
            left++
            right--
        } else {
            result = false
            break
        }
    }
    
    return result
}

アルゴリズム実装(2) $O(n)$

文字の位置を反転させたreversedString文字列とstringの比較:

function isPalindrome(string) {
  const reversedString = []
    for (let i = string.length - 1; 0 <= i; i--) {
        reversedString.push(string[i])
    }
    
    return string === reversedString.join('')
}