समस्या
एक स्ट्रिंग दी गई है, प्रत्येक वर्ण को वर्णमाला में उसके ठीक पहले या ठीक बाद के वर्ण में बदला जाना चाहिए ('a' केवल 'b' बन सकता है, 'z' केवल 'y')। निर्धारित करें कि क्या इन परिवर्तनों का कोई परिणाम पालिंड्रोम हो सकता है।
उदाहरण
const str = 'adfa';
const canFormPalindrome = (str = '') => {
const middle = str.length / 2;
for (let i = 0; i < middle; i++) {
const first = str[i].charCodeAt();
const last = str[str.length - (i + 1)].charCodeAt();
const distance = Math.abs(last - first);
if (distance > 2 || distance === 1) {
return false;
}
}
return true;
};
console.log(canFormPalindrome(str)); // trueआउटपुट
true
व्याख्या
- स्ट्रिंग के दोनों सिरों से केंद्र की ओर तुलना की जाती है।
- प्रत्येक जोड़ी के लिए, उनके ASCII कोड का अंतर निकाला जाता है।
- यदि अंतर 1 है, तो वे एक-दूसरे के पड़ोसी हैं लेकिन दोनों को एक ही दिशा में बदलने पर वे समान नहीं हो सकते।
- यदि अंतर > 2 है, तो उन्हें पड़ोसी परिवर्तनों द्वारा समान नहीं बनाया जा सकता।
- अन्यथा (अंतर 0 या 2), उन्हें समान बनाया जा सकता है।
यह एल्गोरिदम O(n) समय में चलता है और O(1) स्थान का उपयोग करता है।
