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

ကျွန်တော်တို့ဒီနေ့ solve လုပ်မယ့် problem ကတော့ Valid anagram ဘဲဖြစ်ပါတယ်။ Leetcode က Question တစ်ခုဘဲဖြစ်ပါတယ်။

ပထမဦးဆုံး Question ကိုတစ်ချက်ကြည့်လိုက်ရအောင် string နှစ်ခုပေးမယ် s နှင့် t ဆိုပြီးတော့။ အဲ့ဒါကိုကျွန်တော်တို့စစ်ကမှာက t is an anagram of s ဖြစ်လားဆိုတာကိုပါဘဲ။ Question မှာမှတ်ချက်ပါသေးတယ်။ ဘာလဲဆိုရင် string တွေက lowercase alphabets တွေဘဲပါပါ့မယ်တဲ့။ Follow up မေးနိုင်တာကတော့ input မျာ unicode characters တွေပါရင်ဘယ်လိုဖြေရှင်းမလဲတဲ့။

အဖြေမစခင် Anagram ဆိုတာဘာလဲနှင့် Example တစ်ချို့ကိုအရင်ကြည့်လိုက်ရအောင်။ Anagram ဆိုတာဘာကိုပြောတာလဲဆိုရင် string နှစ်ခု length အတူတူဖြစ်ပြီးပြန်စီထားတာကိုဆိုလိုတာ။ ဥပမာဗျာ… Listen ကို silent ပြောင်းတာလိုမျိုး။ ဒါကို anagram ဖြစ်တယ်လို့ပြောလို့ရတယ်။

LeetCode မှာပေးထားတဲ့ example ကိုတစ်ချက်ကြည့်လိုက်ရအောင်…

Input: s = "anagram", t = "nagaram"
Output: true

Input: s = "rat", t = "car"
Output: false

ဒီ question ကိုဖြေလို့ရတဲ့နည်း ၂ နည်းရှိတယ်။ တစ်နည်းက sorted နည်းနှင့် နောက်တစ်နည်းက Hash Table အသုံးပြုတဲ့နည်း။ ကျွန်တော်တို့ဒီ post မှာ sorted array နည်းနှင့်ဖြေပါမယ်။ Hash ကိုသတ်သတ်သေချာရှင်းပြပြီးခါမှ Hash နှင့်အဖြေကိုဒီမှာ update လုပ်ပေးပါ့မယ်။

Sorting Approach

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    return s.split('').sort().join('') === t.split('').sort().join('');
};

အဖြေကတော်တော်လေးရှင်းပါတယ်။ string နှစ်ခုကို array ပြောင်းပြီးတော့ sort လုပ်ပြီး === ဖြစ်လားစစ်လိုက်တာ။ Time complexity က O(nlogn) ပါ။ Space complexity ကတော့ O(n)။

Hash Table Approach, coming soon