Palindrome / قرینه
PalindromePalindrome رشته یا دنباله‌ای است که بعد از normalization تعریف‌شده در مسئله، از چپ و راست یکسان خوانده می‌شود.
اول این مفهوم را در ذهن نگه دار
Palindrome رشته یا دنباله‌ای است که بعد از normalization تعریف‌شده در مسئله، از چپ و راست یکسان خوانده می‌شود.
چطور کار می‌کند؟ ساده و مرحله‌ای
با Two Pointer از دو سر می‌توان در O(n) زمان و با حافظه اضافی کم مقایسه کرد.
قبل از حل روشن کن که فاصله، punctuation و بزرگی/کوچکی حروف باید نادیده گرفته شوند یا نه.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
فرض‌های Unicode، case و normalization را روشن کن.
indexها یا prefix state را تعریف کن.
اگر الگوریتم اجازه می‌دهد اطلاعات match قبلی را reuse کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای Palindrome / قرینه هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function isPalindrome(text) {
const s = text.toLowerCase().replace(/[^a-z0-9]/g, "");
let l = 0, r = s.length - 1;
while (l < r) {
if (s[l++] !== s[r--]) return false;
}
return true;
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
Varies by implementation / input constraints
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی جست‌وجو روی متن بزرگ یا تکراری است و روش naive گران می‌شود از الگوریتم تخصصی استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- نادیده گرفتن Unicode.
- قاطی کردن Substring و Subsequence.
- خطای index/prefix.
مدل یک پاسخ حرفه‌ای
اول ruleهای ورودی را روشن کن؛ خیلی از جواب‌های اشتباه در واقع مسئله normalization متفاوتی را حل می‌کنند.
Palindrome / قرینه چه مسئله‌ای را حل می‌کند؟
Palindrome رشته یا دنباله‌ای است که بعد از normalization تعریف‌شده در مسئله، از چپ و راست یکسان خوانده می‌شود.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا Varies by implementation / input constraints است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
نادیده گرفتن Unicode.