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

ဒီ Problem က Leetcode ရဲ့ Valid Palindrome ကို solve လုပ်ထားတာဘဲဖြစ်ပါတယ်။ ပေးထားတဲ့ String S က palindrome ဖြစ်တယ်ဆိုရင် true return ပြန်ရမှာဖြစ်ပြီးတော့ မဟုတ်ဘူးဆိုရင် false return ပြန်ရမှာဖြစ်ပါတယ်။

ဒီနေရာမှာ Palindrome ဆိုတာကိုနားမလည်ရင် Problem solve လုပ်ဖို့ရာမလွယ်ပါဘူး။ Palindrome ဆိုတာပေးထားတဲ့ string ကိုနောက်ကနေ reverse ပြန်ရင်လည်းအတူတူဖြစ်တာမျိုးကိုပြောတာပါ… အောက်ကနမူနာကိုကြည့်ရင်ပိုရှင်းမယ်ထင်တယ်။

"A man, a plan, a canal: Panama" က Palindrome ပါ
"race a car" ဆိုတာက Palindrome မဟုတ်ပါဘူး။

ကျွန်တော်တို့ဒီနေရာမှာ palindrome က backward, punctuation, case နှင့် spacing တွေကို ignore လုပ်တယ်ဆိုတာကိုလည်းတစ်ချက်သတိမူရမှာဖြစ်ပါတယ်။

တကယ်လို့ဒီမေးခွန်းကို အင်တာဗျူးမှာမေးတယ်ဆိုရင် ကျွန်တော်တို့ဘက်က empty string ဆိုရင်ကော valid palindrome ဟုတ်လားဆိုတာမျိုးမေးရမှာပါ။ များသောအားဖြင့်တော့ empty string က valid palindrome လို့သတ်မှတ်ကြပါတယ်။ ကိုယ့်ဘက်ကသေချာအောင်တော့မေးရမှာပေါ့။

ကျွန်တော်အောက်မှာ example test case လေးဖော်ပြထားပါတယ်… ကိုယ်တိုင်စမ်းသတ်ရေးကြည့်ပြီးစမ်းကြည့်နိုင်ပါတယ်။

palindrome(“race car”) should return true
palindrome(“never odd or even”) should return true
palindrome(“nope”) should return false
palindrome(“1 eye for of 1 eye.”) should return false
palindrome(“0_0 (: /-\ :) 0–0”) should return true

ကျွန်တော်ဒီ Problem ကိုဘယ်လို Solve လုပ်သလဲတစ်ချက်ကြည့်လိုက်ရအောင်…

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    var s = s.replace(/[^a-zA-Z0-9]/g, "").toLowerCase(), i = 0, j = s.length - 1;
    
    if (s.length == 0) { return true; }
    
    while(i < j) {
        if(s[i] !== s[j]) return false;
        i++; j--;
    }
    return true;
};

ကျွန်တော်ပထမဆုံး string ကို regular expression သုံးပြီး replace လုပ်လိုက်တယ် နောက် Lowercase ပြောင်းလိုက်တယ်။ ပြီးတော့ left pointer, right pointer သုံးပြီးတော့ while loop ပတ်ပြီးတော့ palindrom ဖြစ်လားစစ်လိုက်တယ်။ ဒီနေရာမှာကျွန်တော် while loop ကိုသုံးတာက invalid ဖြစ်တဲ့ကောင်ဆိုမြန်မြန်ဆန်ဆန် false return ပြန်ရအောင်လုပ်လိုက်တာပါ။ Worst case မှာဒီကောင်လည်း O(n) ဖြစ်ပြီး While loop လည်း O(n) ဘဲဖြစ်ပါတယ်။

Time Complexity က O(n) ဖြစ်ပြီးတော့ Space လည်း O(1) ဖြစ်ပါတယ်။