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

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

پالیندروم

پالیندروم (Palindrome) از مفاهیم پرکاربرد و از sub-problem های پرتکرار در سوالات الگوریتمی است. به واژه، جمله، عدد، شعر یا هر چیز دیگری گفته می‌شود که خواندن آن از چپ به راست یا از راست به چپ کاملاً یکسان باشد، مثلا عدد “42324” و کلمه‌ی “نادان”. عبارتی مثل “race car” هم با حذف فاصله، پالیندروم خواهد بود. معمولا فرض بر این است که فاصله‌ها، ویرگول‌ها و هر کاراکتری غیر از الفبا و اعداد را نادیده می‌گیریم. همچنین کوچک یا بزرگ بودن حروف مهم نیست.

 

استراتژی‌های سوالات پالیندروم

برای تشخیص پالیندروم بودن یک رشته، چند استراتژی رو میشه به کار برد:

  • یک پوینتر در سمت چپ‌ترین کاراکتر و یک پوینتر در سمت راست‌ترین کاراکتر قرار می‌دیم. در هر حرکت، پوینتر سمت چپ رو یک واحد به راست و پوینتر سمت راست رو یک واحد به چپ حرکت می‌دیم و چک میکنیم کاراکترهایی که الان پوینترها روی اونها هستن، یکسان باشن. با فرض پالیندروم بودن ورودی، در نهایت اگه تعداد کاراکترهای رشته ورودی فرد باشه، هر دو پوینتر روی یک کاراکتر (کاراکتر وسط) قرار می‌گیرن و اگه تعداد کاراکترهای رشته ورودی زوج باشه، پوینترها روی دو کاراکتر میانی که یکسان هستن قرار می‌گیرن.
  • مشابه مورد قبل، اما برعکس. پوینترهارو روی کاراکتر میانی (در صورت فرد بودن تعداد کاراکترهای رشته ورودی) یا کاراکترهای میانی (در صورت زوج بودن تعداد کاراکترهای رشته ورودی) قرار میدیم. در هر حرکت، پوینتر سمت چپ رو یک واحد به چپ و پوینتر سمت راست رو یک واحد به راست حرکت می‌دیم و چک میکنیم کاراکترهایی که الان پوینترها روی اونها هستن، یکسان باشن.
  • رشته ورودی رو reverse می‌کنیم و این دو رشته رو با هم مقایسه می‌کنیم. مثلا به این صورت که از پوینتر اول رو روی کاراکتر اول رشته ورودی و پوینتر دوم رو روی کاراکتر اول رشته reverse شده قرار می‌دیم و در هر حرکت جلو میریم و کاراکترها رو با هم مقایسه می‌کنیم.

شرایط مسئله

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

نوشتن test case

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
input = "aabaa"
output = true
input = "aabbaa"
output = true
input = "abc"
output = false
input = "a"
output = true
input = ""
output = true
input = "A man, a plan, a canal : Panama"
output = true

راه حل منطقی

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {

    public bool IsPalindrome(string s) {
    
    s = Regex.Replace(s, "[^A-Za-z0-9]", "").ToLower();

    int left = 0;
    int right = s.Length - 1;

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

        left++;
        right--;
    }

    return true;

    }
}

منابع

udemy