Palindrome به رشته، عدد یا دنباله‌ای گفته می‌شود که اگر آن را از ابتدا به انتها یا از انتها به ابتدا بخوانیم، یک نتیجه به دست آوریم.

برای مثال:

racecar
level
madam
1221

همگی Palindrome هستند.

اما:

hello
algorithm
1234

Palindrome نیستند.

مسئله Palindrome Checking یکی از ساده‌ترین ولی مهم‌ترین مسائل String Algorithms است و معمولاً برای آموزش مفاهیمی مانند Two Pointers، String Traversal، Recursion و Optimization استفاده می‌شود.

تعریف ساده Palindrome

رشته زیر را در نظر بگیرید:

racecar

اگر آن را برعکس کنیم:

racecar

همان مقدار اولیه را به دست می‌آوریم.

بنابراین:

racecar = Palindrome

اما برای:

hello

برعکس آن:

olleh

است و برابر نیست.

پس:

hello ≠ Palindrome

ساده‌ترین روش: Reverse کردن رشته

اولین راهی که معمولاً به ذهن می‌رسد این است که رشته را برعکس کنیم و با مقدار اصلی مقایسه کنیم.

function isPalindrome(value: string): boolean {
  const reversed = value.split("").reverse().join("");
  return value === reversed;
}

console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello"));   // false

این روش بسیار خوانا و ساده است.

اما یک نکته وجود دارد:

برای ساخت رشته معکوس، حافظه جدید مصرف می‌کنیم.

اگر طول رشته n باشد:

Time Complexity: O(n)
Space Complexity: O(n)

برای بسیاری از برنامه‌ها این روش کاملاً مناسب است، اما اگر بخواهیم الگوریتم بهینه‌تری داشته باشیم، می‌توانیم از Two Pointers استفاده کنیم.

روش Two Pointers

در روش Two Pointers دو Pointer در ابتدا و انتهای رشته قرار می‌دهیم.

r a c e c a r
↑           ↑
L           R

سپس کاراکترهای دو طرف را مقایسه می‌کنیم.

اگر برابر باشند:

left++
right--

و به سمت مرکز حرکت می‌کنیم.

r a c e c a r
  ↑       ↑
  L       R

و سپس:

r a c e c a r
    ↑   ↑
    L   R

اگر تمام جفت‌ها برابر باشند، رشته Palindrome است.

اگر حتی یک جفت متفاوت باشد، نتیجه false است.

شبه‌کد

left = 0
right = length - 1

while left < right:
    if string[left] != string[right]:
        return false

    left++
    right--

return true

پیاده‌سازی Two Pointers با TypeScript

function isPalindrome(value: string): boolean {
  let left = 0;
  let right = value.length - 1;

  while (left < right) {
    if (value[left] !== value[right]) {
      return false;
    }

    left++;
    right--;
  }

  return true;
}

console.log(isPalindrome("level"));   // true
console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello"));   // false

در این روش رشته جدیدی ساخته نمی‌شود.

بنابراین:

Time Complexity: O(n)
Space Complexity: O(1)

این یکی از دلایلی است که Two Pointers راه‌حل استاندارد و محبوب برای Palindrome Checking است.

چرا فقط نصف رشته را بررسی می‌کنیم؟

فرض کنید رشته n کاراکتر دارد.

وقتی کاراکتر اول را با آخر مقایسه کردیم، نیازی نیست دوباره همان دو کاراکتر را بررسی کنیم.

بنابراین تنها کافی است تا وسط رشته حرکت کنیم.

برای رشته‌ای با طول فرد:

r a c e c a r
      ↑
    center

کاراکتر وسط نیازی به مقایسه ندارد.

برای رشته با طول زوج:

a b b a
    ↑ ↑

دو Pointer از کنار یکدیگر عبور می‌کنند و بررسی پایان می‌یابد.

Palindrome با فاصله و علائم نگارشی

در مسائل واقعی ممکن است ورودی به شکل زیر باشد:

A man, a plan, a canal: Panama

اگر فاصله‌ها و punctuation را در نظر بگیریم، رشته ظاهراً Palindrome نیست.

اما اگر فقط حروف و اعداد را نگه داریم و حروف را lowercase کنیم:

amanaplanacanalpanama

این رشته Palindrome است.

روش اول: Normalize کردن ورودی

function normalize(value: string): string {
  return value
    .toLowerCase()
    .replace(/[^a-z0-9]/g, "");
}

function isPalindrome(value: string): boolean {
  const normalized = normalize(value);

  let left = 0;
  let right = normalized.length - 1;

  while (left < right) {
    if (normalized[left] !== normalized[right]) {
      return false;
    }

    left++;
    right--;
  }

  return true;
}

مثال:

isPalindrome("A man, a plan, a canal: Panama");
// true

روش بهینه بدون ساخت String جدید

اگر بخواهیم از حافظه اضافی کمتری استفاده کنیم، می‌توانیم هنگام حرکت Pointerها کاراکترهای غیرمجاز را Skip کنیم.

function isAlphaNumeric(char: string): boolean {
  return /[a-z0-9]/i.test(char);
}

function isPalindrome(value: string): boolean {
  let left = 0;
  let right = value.length - 1;

  while (left < right) {
    while (
      left < right &&
      !isAlphaNumeric(value[left])
    ) {
      left++;
    }

    while (
      left < right &&
      !isAlphaNumeric(value[right])
    ) {
      right--;
    }

    if (
      value[left].toLowerCase() !==
      value[right].toLowerCase()
    ) {
      return false;
    }

    left++;
    right--;
  }

  return true;
}

این الگو یکی از مسائل رایج مصاحبه‌های فنی است.

Palindrome برای اعداد

Palindrome فقط مخصوص String نیست.

مثلاً:

121
1221
4554

اعداد Palindrome هستند.

ولی:

123
1231

نیستند.

ساده‌ترین راه تبدیل عدد به String است:

function isNumberPalindrome(value: number): boolean {
  const text = String(value);

  let left = 0;
  let right = text.length - 1;

  while (left < right) {
    if (text[left] !== text[right]) {
      return false;
    }

    left++;
    right--;
  }

  return true;
}

آیا بدون تبدیل عدد به String می‌توان بررسی کرد؟

بله.

می‌توان عدد را از نظر ریاضی Reverse کرد.

برای مثال:

121

Reverse آن نیز:

121

است.

نمونه:

function isNumberPalindrome(value: number): boolean {
  if (value < 0) {
    return false;
  }

  const original = value;
  let reversed = 0;

  while (value > 0) {
    const digit = value % 10;
    reversed = reversed * 10 + digit;
    value = Math.floor(value / 10);
  }

  return original === reversed;
}

اعداد منفی معمولاً Palindrome در نظر گرفته نمی‌شوند، زیرا علامت منفی فقط در یک طرف قرار دارد.

-121

از سمت مقابل:

121-

خواهد بود.

Palindrome با Recursion

مسئله را می‌توان Recursive نیز حل کرد.

ایده:

1. اولین و آخرین کاراکتر را مقایسه کن.
2. اگر متفاوت بودند false.
3. اگر برابر بودند، بخش داخلی را بررسی کن.

function isPalindromeRecursive(
  value: string,
  left = 0,
  right = value.length - 1
): boolean {
  if (left >= right) {
    return true;
  }

  if (value[left] !== value[right]) {
    return false;
  }

  return isPalindromeRecursive(
    value,
    left + 1,
    right - 1
  );
}

از نظر زمان:

O(n)

اما به دلیل Call Stack:

Space Complexity: O(n)

است.

به همین دلیل Two Pointers معمولاً انتخاب بهتری است.

کاربرد Palindrome در الگوریتم‌ها

Palindrome Checking به خودی خود مسئله‌ای ساده است، اما پایه بسیاری از مسائل پیچیده‌تر است.

مثلاً:

• Longest Palindromic Substring
• Palindromic Subsequence
• Palindrome Partitioning
• Minimum Insertions to Make Palindrome
• Valid Palindrome
• Almost Palindrome

در بسیاری از این مسائل، ایده مقایسه متقارن از دو طرف همچنان نقش اصلی دارد.

Almost Palindrome چیست؟

یکی از مسائل رایج این است:

آیا با حذف حداکثر یک کاراکتر می‌توان رشته را Palindrome کرد؟

مثلاً:

abca

اگر b یا c را حذف کنیم، می‌توانیم به یک Palindrome برسیم.

اینجا نیز Two Pointers بسیار مفید است.

وقتی اولین mismatch را پیدا می‌کنیم، دو حالت را امتحان می‌کنیم:

skip left
or
skip right

نمونه:

function isRangePalindrome(
  value: string,
  left: number,
  right: number
): boolean {
  while (left < right) {
    if (value[left] !== value[right]) {
      return false;
    }

    left++;
    right--;
  }

  return true;
}

function validPalindrome(value: string): boolean {
  let left = 0;
  let right = value.length - 1;

  while (left < right) {
    if (value[left] !== value[right]) {
      return (
        isRangePalindrome(value, left + 1, right) ||
        isRangePalindrome(value, left, right - 1)
      );
    }

    left++;
    right--;
  }

  return true;
}

این مسئله نمونه خوبی برای ترکیب Two Pointers و Branching محدود است.

Palindrome در DNA و Sequence Analysis

در علوم زیستی برخی Sequenceها ساختار متقارن یا شبه‌متقارن دارند.

البته مفهوم biological palindrome دقیقاً همیشه معادل String Palindrome ساده نیست، زیرا در DNA معمولاً Complement نیز اهمیت دارد.

اما از دید الگوریتمی، بررسی تقارن Sequenceها یکی از کاربردهای مفاهیم مشابه است.

Palindrome در پردازش متن

Palindrome Checking می‌تواند در ابزارهای تحلیل متن، بازی‌های کلمه‌ای، Puzzleها و پردازش داده استفاده شود.

در عمل، ارزش اصلی این مسئله برای Developerها معمولاً آموزش Pattern الگوریتمی آن است:

Two Pointers
↓
Compare symmetric positions
↓
Move toward center

همین Pattern در مسائل زیادی استفاده می‌شود.

Two Pointers چرا مهم است؟

Two Pointers تنها مخصوص Palindrome نیست.

این تکنیک در مسائلی مانند:

• Pair Sum در Array مرتب‌شده
• Remove Duplicates
• Container With Most Water
• Merge Operations
• Partitioning
• Sliding Windowهای خاص

نیز استفاده می‌شود.

بنابراین مسئله Palindrome یکی از بهترین مثال‌ها برای یادگیری این تکنیک است.

Unicode و یک نکته مهم برای JavaScript

در JavaScript و TypeScript، Index کردن String همیشه به معنای پردازش کامل Unicode Character نیست.

برخی Emojiها یا Unicode Symbolها ممکن است از چند Code Unit تشکیل شده باشند.

برای ورودی‌های عادی انگلیسی الگوریتم ساده کافی است، اما برای سیستم‌های Unicode-aware ممکن است نیاز به تبدیل رشته به مجموعه‌ای از Code Pointها یا استفاده از ابزارهای مناسب Unicode داشته باشیم.

مثلاً:

const chars = Array.from(value);

در بسیاری از موارد نسبت به Index مستقیم String رفتار مناسب‌تری برای Code Pointها خواهد داشت.

Case Sensitivity

رشته:

Level

در مقایسه Case-sensitive، Palindrome نیست چون:

L !== l

اما پس از lowercase:

level

Palindrome است.

پس باید قبل از پیاده‌سازی مشخص کنیم Business Rule چیست.

یک سؤال رایج مصاحبه

یکی از سؤال‌های کلاسیک:

یک String داده شده است. با نادیده گرفتن فاصله‌ها، علائم نگارشی و تفاوت حروف بزرگ و کوچک بررسی کنید آیا Palindrome است یا خیر.

مثال:

Input:
"A man, a plan, a canal: Panama"

Output:
true

راه‌حل مناسب:

Two Pointers
+ Skip non-alphanumeric characters
+ Case-insensitive comparison

پیچیدگی:

Time: O(n)
Space: O(1)

در نسخه‌ای که بدون ساخت رشته Normalize‌شده اجرا شود.

اشتباهات رایج

1. مقایسه نکردن ورودی Normalize‌شده

در مسائل واقعی باید مشخص کنیم:

• فاصله مهم است؟
• punctuation مهم است؟
• Case مهم است؟
• Unicode چگونه مدیریت می‌شود؟

2. استفاده غیرضروری از Reverse

روش Reverse اشتباه نیست، اما در مصاحبه ممکن است از شما راه‌حل O(1) Space خواسته شود.

در آن صورت Two Pointers گزینه مناسب‌تری است.

3. اشتباه در شرط حلقه

شرط مناسب معمولاً:

left < right

است.

وقتی Pointerها به هم برسند یا از هم عبور کنند، تمام جفت‌ها بررسی شده‌اند.

4. فراموش کردن Empty String

رشته خالی معمولاً Palindrome در نظر گرفته می‌شود، زیرا هیچ جفت متناقضی وجود ندارد.

همچنین String تک‌کاراکتری نیز Palindrome است.

""
"a"

هر دو نتیجه true دارند.

Edge Caseها

""        → true
"a"       → true
"aa"      → true
"ab"      → false
"racecar" → true
"Racecar" → depends on normalization
"121"     → true

تعریف دقیق رفتار باید متناسب با مسئله تعیین شود.

Reverse vs Two Pointers

Reverse

Time:  O(n)
Space: O(n)

مزایا:

• ساده
• خوانا
• پیاده‌سازی سریع

Two Pointers

Time:  O(n)
Space: O(1)

مزایا:

• بدون ساخت Copy اضافی
• مناسب مصاحبه‌ها
• قابل گسترش برای مسائل پیچیده‌تر

بنابراین برای آموزش الگوریتمی، Two Pointers معمولاً انتخاب بهتر است.

جمع‌بندی

Palindrome رشته یا دنباله‌ای است که از دو جهت یکسان خوانده می‌شود.

ساده‌ترین مثال:

racecar

راه‌حل استاندارد برای تشخیص Palindrome استفاده از Two Pointers است:

left → start
right → end

compare
↓
move inward

پیچیدگی این روش:

Time Complexity: O(n)
Space Complexity: O(1)

اما اهمیت واقعی این مسئله فقط در تشخیص چند کلمه قرینه نیست.

Palindrome Checking یکی از ساده‌ترین راه‌ها برای یادگیری تفکر Two Pointers، بررسی متقارن، مدیریت Edge Caseها و Optimization حافظه است و مقدمه‌ای برای مسائل پیچیده‌تری مانند Longest Palindromic Substring و Palindrome Partitioning محسوب می‌شود.