برای دسترسی به سوال 680 لیت‌کد میتونید از این لینک استفاده کنید. سطح این سوال Easy است.

اگر پیشنهادی برای اصلاح پست دارید، می‌تونید از طریق دکمه‌ی "پیشنهاد اصلاح متن" وارد ریپازیتوری وبلاگ در github بشید و تغییرات مورد نظرتون رو پیشنهاد بدید.

شبه‌پالیندروم

رشته‌ی Almost Palindrome (شبه‌پالیندروم)، به رشته‌ای گفته می‌شه که با حذف یک کاراکتر، به Palindrome تبدیل میشه. مثلا “race a car” پالیندروم نیست، اما با حذف کاراکتر ‘a’ یا ’e’ به پالیندروم تبدیل می‌شه. پس شبه‌پالیندرومه!

شرایط مسئله

در این مرحله، شرایط خاص مسئله و حالت‌های edge case رو بررسی می‌کنیم. این شرایط باید در توضیحات سوال یا مثال‌ها مشخص شده باشن یا اینکه از پاسخ‌های پیش فرض استفاده کنیم. طبق تعریفی که برای پالیندروم داریم، کاراکترهای غیر از الفبا و عدد در نظر گرفته نمی‍شوند و کوچک و بزرگ بودن حروف هم مهم نیست.

  • آیا یک پالیندروم، شبه‌پالیندروم است؟ بله. مثلا “aba” یک پالیندروم است و شبه‌پالیندروم هم در نظر گرفته می‌شود.

نوشتن test case

در این مرحله، چند مثال می‌نویسیم که هم شرایط خواسته شده و هم edge case هایی که بالاتر اشاره کردیم رو pass کنه.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
input = "race a car"
output = true
input = "abccdba"
output = true
input = "abcdefdba"
output = false
input = "a"
output = true
input = ""
output = true
input = "ab"
output = true

راه حل منطقی

در این مرحله به دنبال working solution هستیم، یعنی راه حلی منطقی که بتونه مسئله رو حل کنه. به راه حل بهینه فکر نمی‌کنیم. درگیر زبان برنامه نویسی و محدودیت‌های اون هم نخواهیم بود.

چالش اصلی، پیدا کردن کاراکتری است که باعث شده رشته از پالیندروم به شبه‌پالیندروم تبدیل بشه. از طرفی اگر یک رشته پالیندروم باشه، شبه‌پالیندروم هم هست. کدام یک از سه استراتژی کاربردی در مورد پالیندروم‌ها اینجا می‌تونه استراتژی ایده‌آل باشه؟

استراتژی Reverse کمک زیادی نمی‌کنه، ابتدا رشته رو برعکس می‌کنه و سپس در مرحله quality check، بررسی می‌کنه این دو رشته یکسان هستن یا نه. این نوع بررسی، اطلاعاتی در مورد کاراکترهایی که باعث conflict شدن نمیده.

استراتژی Pointers from outside از لحاظ پیچیدگی زمانی و حافظه‌ای تفاوتی با Pointers from center نداره اما پیاد‌ه‌سازی ساده‌تری داره. پس پیاده‌اش می‌کنیم. وقتی از طرفینِ رشته به طرف کاراکتر(های) میانی حرکت می‌کنیم، اگه پالیندروم نباشه، در جایی به conflict برخورد می‌کنیم. یعنی پوینترها روی کاراکترهایی قرار می‌گیرند که یکسان نیستند. در این حالت دو رشته تولید می‌کنیم، یکی با حذف کاراکتری که پوینتر راست روی اون هست و یکی با حذف کاراکتری که پوینتر چپ روی اون هست.

مثلا رشته “abccdba” رو داریم. پوینترها یک یکی جلو میرن تا به حروف غیر یکسان برسند. “abccdba” جاییه که حروف غیر یکسان دیده میشه. حالا دو رشته “abccba” و “abcdba” رو تولید می‌کنیم که از حذف کاراکترهای conflict‌دار به وجود اومدن. نکته مهم اینه که نیاز نیست در رشته‌های جدید، بررسی کاراکترها رو از ابتدا انجام بدیم. حروف آبی رنگ قبلا بررسی شدن و یکسان بودنشون تایید شده. بررسی رو ادامه می‌دیم تا به کاراکتر(های) میانی برسیم. عمل حذف کاراکتر conflict‌دار فقط یک بار میتونه رخ بده، اگه در انتها، رشته‌ی باقیمانده، پالیندروم بود، رشته‌ی ابتدایی، شبه‌پالیندروم بوده.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public bool ValidPalindrome(string s) {
  int start = 0;
  int end = s.Length - 1;

  while (start < end) {
    if (s[start] != s[end]) {
      return ValidSubPalindrome(s, start + 1, end) || ValidSubPalindrome(s, start, end - 1);
    }
    start++;
    end--;
  }

  return true;
}

public bool ValidSubPalindrome(string s, int start, int end) {
  while (start < end) {
    if (s[start] != s[end]) {
      return false;
    }
    start++;
    end--;
  }
  return true;
}

پیچیدگی زمانی و حافظه‌ای

در این مرحله به بررسی پیچیدگی زمانی و حافظه ای راه حل می‌پردازیم. یعنی تحلیل می‌کنیم که بین زمان اجرای الگوریتم و حافظه مصرفی آن، چه رابطه ای با اندازه ورودی الگوریتم وجود دارد.

پیچیدگی زمانی الگوریتم O(n) و پیچیدگی حافظه‌ای O(1) است.

منابع

udemy