မှတ်ချက် – ဒီ Post သည် Algorithm Interview Preparation အပိုင်းဆက်ဖြစ်သည်။

Leetcode မေးခွန်းကိုကြည့်ရန် ဒီ Link ကိုနှိပ်ပါ။

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

 

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.
 

Constraints:

1 <= s.length <= 2 * 105
s consists only of printable ASCII characters.

---

ဒီ problem ကဘာလဲဆို Palindrome ဟုတ်မဟုတ်စစ်ရမှာပေါ့။ Palindrome ဆိုတာဘာလဲဆိုရင် ရှေ့နှင့်နောက်နှင့်ညီနေတာမျိုး ဥပမာ "A man, a plan, a canal: Panama" သူ့ကိုကြည့်လိုက်မယ်ဆိုရင် ရှေ့နှင့်နောက်နှင့်ညီနေတာ ဒါမျိုးကိုပြောတာပေါ့။

problem ကပြောထားတာက uppercase letters တွေကို lower case ပြောင်း non-alphanumeric တွေကို remove လုပ်ရမယ်။ ရှေ့ကဖတ်ဖတ် နောက်ကဖတ်ဖတ်တူကမယ်။ တူတယ်ဆိုရင် true မတူဘူးဆိုရင် false ပြန်ရမယ်။

ပထမဆုံးစဥ်းစားမိတာက သူ့ problem ထဲကအတိုင်းဘဲလုပ်တာပေါ့။ ပေးလိုက်တဲ့ phrase ကို non-alphanumeric တွေကို remove လုပ် lowercase ပြောင်းပီးတော့ string reverse လုပ်ပီးစစ်လိုက်တာပေါ့။ သူ့ရဲ့ Time Complexity က O(n) ဖြစ်ပီးတော့ Space Complexity ကလဲ O(n) ဘဲ။

var isPalindrome = function(s) {
    const re = /[^A-Za-z0-9]/g;
    s = s.toLowerCase().replace(re, '');
    
    return s == s.split('').reverse().join('')
};

---

နောက်တနည်းကတော့ 2 Pointers သုံးပီးတော့ရှင်းတာ။ Pointer 2 ခုရှိမယ် Left နဲ့ Right ဆိုပီးတော့အဲ့ကနေတဖြေးဖြေးဝင်လာပီးတော့စစ်တာပေါ့… ဒါဆို non alphanumeric တွေဆိုဘယ်လိုလုပ်မလဲဆိုတော့ ascii-code ကိုသုံးပီးတော့ ignore လုပ်လိုက်မယ်။ code ကိုကြည့်ရင်ပိုရှင်းသွားမယ်ထင်တယ်။

function isAlphaNum(c) {
    let charCode = c.charCodeAt(0);
    return (charCode >= 65 && charCode <= 90) || // A-Z
           (charCode >= 97 && charCode <= 122) || // a-z
           (charCode >= 48 && charCode <= 57); // 0-9
}

function isPalindrome(s) {
    let l = 0, r = s.length - 1;

    while (l < r) {
        // Move left pointer to the next alphanumeric character
        while (l < r && !isAlphaNum(s[l])) {
            l++;
        }

        // Move right pointer to the previous alphanumeric character
        while (r > l && !isAlphaNum(s[r])) {
            r--;
        }

        // Compare characters
        if (s[l].toLowerCase() !== s[r].toLowerCase()) {
            return false;
        }

        l++;
        r--;
    }

    return true;
}

Code ကိုတချက်ပြန်ရှင်းပြလိုက်မယ်။ isAlphaNum(c) ဆိုတာကဘာလဲဆိုရင် ပေးလိုက်တဲ့ string က alpha numeric ဖြစ်မဖြစ်စစ်တာပေါ့။ ဘယ်လိုစစ်လဲဆိုရင် ပေးလိုက်တဲ့ string က A-Z ascii code အတွင်းမှာလား a-z အတွင်းမှာလား 0-9 အတွင်းမှာလားဆိုပီးစစ်လိုက်တာ။ အဲ့ကောင်တွေမဟုတ်ဘူးဆိုရင် func က false return ပြန်လိမ့်မယ်။

Main func ဖြစ်တဲ့ isPalindrome မှာဆိုရင်အထက်မှာပြောခဲ့သလိုဘဲ pointer 2 ခုရှိမယ် l နှင့် r ဆိုပီးတော့။ ပီးရင် while loop ပတ်ထားမယ်။ တကယ်လို့ l pointer က r ထက်လဲသေးမယ် alphanum လဲမဖြစ်ဘူးဆိုရင်သူ့ကို skip လိုက်မယ်။ r pointer လဲထိုနည်းအတိုင်းဘဲ။

left နဲ့ right နဲ့တူလားစစ်မယ် မတူရင်နောက်ကဟာတွေဆက်မစစ်တော့ဘဲ false. ပြန်လိုက်မယ်။ တူသေးတယ်ဆိုရင် left pointer ကိုတိုးပီးတော့ right pointer ကိုလျှော့မယ် နောက်ဆုံးမတူတာတွေမတွေ့ဘဲ while loop ပီးသွားရင် return true ပြန်မယ်အဲ့လိုမျိုးပေါ့။

အပေါ်မှာရှင်းရှင်းလေးကိုဘာလို့ pointer တွေသုံးပီးတော့ဖြေရှင်းရလဲဆိုရင် ဒီ soluction က Time က O(n) ဖြစ်ပီးတော့ Space O(1) ဖြစ်တယ်။ တချို့ situration တွေမှာ Space optimize လုပ်ချင်တာမျိုးတွေဆိုဒါမျိုးသုံးရမှာပေါ့။ အင်တာဗျူးမှာဆိုရင် interview မေးခွန်းမေးတဲ့သူက Space O(1) နဲ့ရှင်းပါဆိုတာမျိုးဖြစ်နိုင်တာဘဲ။

---

English လို Neetcode ရှင်းပြထားတာကိုကြည့်ချင်တယ်ဆိုရင် အောက်ဖော်ပြပါ YouTube video ကိုကြည့်နိုင်ပါတယ်။