How to use Hashing In Javascript
Using hashing, the approach compares the original string’s hash with the hashes of all its rotations. If any rotation’s hash matches, it verifies if the substring is a palindrome, determining if the string is a rotation of a palindrome.
Example:
function isRotationOfPalindrome(str) {
function isPalindrome(s) {
return s === s.split('').reverse().join('');
}
function computeHash(s) {
let hash = 0;
for (let i = 0; i < s.length; i++) {
hash = (hash * 31 + s.charCodeAt(i)) % (1e9 + 7);
}
return hash;
}
let originalHash = computeHash(str);
let n = str.length;
let power = 1;
let currentHash = 0;
for (let i = 0; i < n; i++) {
currentHash = (currentHash * 31 + str.charCodeAt(i)) % (1e9 + 7);
if (i < n - 1) {
power = (power * 31) % (1e9 + 7);
}
}
for (let i = 0; i < n; i++) {
if (currentHash === originalHash && isPalindrome(str.slice(i) + str.slice(0, i))) {
return true;
}
currentHash = (currentHash - (str.charCodeAt(i) * power) % (1e9 + 7) + (1e9 + 7)) % (1e9 + 7);
currentHash = (currentHash * 31 + str.charCodeAt((i + n) % n)) % (1e9 + 7);
}
return false;
}
console.log(isRotationOfPalindrome("abcd")); // false
console.log(isRotationOfPalindrome("aab")); // true
Output
false false
JavaScript Program to Check if a Given String is a Rotation of a Palindrome
In this article, we will see how to check a given string is a rotation of a palindrome. A palindrome is a string that remains the same when its characters are reversed (e.g., “racecar” is a palindrome).
Example:
Input: str = "racecar"
Output: true
// "racecar" is a rotation of a palindrome "racecar"
Input: str = "abbab"
Output: true
// "abbab" is a rotation of "abbba".
Input: str = "baba"
Output: true
// "baba" is a rotation of a palindrome "baba".
Input: str = "abcd"
Output: false
// "abcd" is not a rotation of any palimdrome.
Table of Content
- Naive Approach
- Efficient Approach:
- Using Hashing