Palindrome Check (回文チェック) アルゴリズム
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('') }