روز 09/90: تسلط بر طولانی ترین بستر پالیندرومیک – تکنیک گسترش مرکز در TypeScript

مقدمه
امروز ما در حال حل یکی از مشکلات رشته ای کلاسیک LeetCode هستیم – پیدا کردن طولانی ترین بستر palindromic. این مشکل شماره 5 است و یک روش عالی برای درک برنامه نویسی پویا و تکنیک های گسترش مرکز در الگوریتم های رشته است.

مشکل
با توجه به یک رشته s، طولانی ترین بستر را که همان رو به جلو و عقب را می خواند ، برگردانید (یک پالندروم).

مثال:
''
ورودی: “باباد”
خروجی: “باب” یا “ابا”
توضیح: هر دو “BAB” و “ABA” زیرزمین های معتبر Palindromic هستند.
''

راه حل بهینه
'' 'Typescript
عملکرد طولانی ترین پالیندروم (s: رشته): رشته {
بگذارید شروع کنید = 0 ؛
اجازه دهید پایان = 0 ؛

for (let i = 0; i < s.length; i++) {
    const [left1, right1] = expandAroundCenter(s, i, i);
    const [left2, right2] = expandAroundCenter(s, i, i + 1);

    if (right1 - left1 > end - start) {
        start = left1;
        end = right1;
    }
    if (right2 - left2 > end - start) {
        start = left2;
        end = right2;
    }
}

return s.substring(start, end + 1);

}

عملکرد ExpandAroundCenter (S: String ، سمت چپ: شماره ، راست: شماره): [number, number] {
در حالی که (سمت چپ> = 0 && راست چپ-
راست ++ ؛
}
بازگشت [left + 1, right – 1]؛
}
''

این راه حل:
✅ کارآمد – O (N²) پیچیدگی زمانی (بهینه برای این مشکل)
✅ بهینه سازی شده فضا – o (1) فضای اضافی
✅ تمیز – از منطق توسعه مرکز ساده استفاده می کند
palindromes عجیب و غریب و حتی طول

چگونه کار می کند
تکنیک انبساط مرکز: هر شخصیت (و بین کاراکترها) را به عنوان مراکز بالقوه پالیندروم بررسی می کند

گسترش دوگانه: برای هر دو palindromes با طول عجیب و غریب (مرکز تک) و یکنواخت (مرکز دوگانه) گسترش می یابد

ردیابی مرزها: شاخص های شروع/پایان طولانی ترین پالندروم موجود را حفظ می کند

مقایسه طول: هنگامی که پالندروم های طولانی تر پیدا می شوند ، به طور مداوم به روز می شوند

رویکردهای جایگزین
رویکرد برنامه نویسی پویا:
'' 'Typescript
عملکرد طولانی ترین پالیندروم (s: رشته): رشته {
const n = s.l طول ؛
Const DP: بولی[][] = Array (n) .fill (false) .map (() => array (n) .fill (false)) ؛
اجازه دهید نتیجه = “” ؛

for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
        dp[i][j] = s[i] === s[j] && (j - i < 3 || dp[i + 1][j - 1]);
        if (dp[i][j] && j - i + 1 > result.length) {
            result = s.substring(i, j + 1);
        }
    }
}
return result;

}
''
جوانب:

• رویکرد سیستماتیک با استفاده از جدول DP
• درک رابطه عود آسان تر است

منفی:

• O (n²) پیچیدگی فضایی
• اجرای پیچیده تر
• به دلیل اولیه سازی جدول کندتر

رویکرد نیروی بی رحمانه:
'' 'Typescript
عملکرد طولانی ترین پالیندروم (s: رشته): رشته {
اجازه دهید طولانی ترین = “” ؛
برای (اجازه دهید i = 0 ؛ i برای (اجازه دهید j = i ؛ j const subtr = s.substring (i ، j + 1) ؛
if (ispalindrome (subtr) && subtr.l طول> طولانی ترین.l طول) {
طولانی ترین = subtr ؛
}
}
}
بازگشت طولانی ترین ؛
}

عملکرد Ispalindrome (S: String): Boolean {
بازگشت s === s.split (''). معکوس (). بپیوندید ('') ؛
}
''
جوانب:

• درک ساده
• هیچ مفاهیم پیشرفته ای لازم نیست

منفی:

• O (n³) پیچیدگی زمان
• برای رشته های طولانی تر بسیار ناکارآمد است

موارد لبه مورد توجه

• رشته
• رشته تک شخصیت (“A”)
• همه شخصیت های یکسان (“aaaaa”)
• بدون palindromes طولانی تر از 1 کاراکتر (“abcde”)
• Palindromes یکنواخت (“ABBA”)
• مورد مختلط با شخصیت های خاص

ملاحظات عملکرد
راه حل بهینه:

• هر شخصیت را به عنوان یک مرکز بالقوه پردازش می کند
• در زمان O (n) در هر مرکز گسترش می یابد
• پیچیدگی زمانی کل O (n²) (بهینه برای این مشکل)
• از فضای ثابت استفاده می کند (فقط شاخص ها را ذخیره می کند)

اشتباهات رایج برای جلوگیری از

• فراموش کردن هر دو palindroms عجیب و غریب و حتی طول
• مرزهای نادرست هنگام گسترش از مرکز
• به روزرسانی طولانی ترین Palindrome به درستی
• خطاهای خارج از یک در استخراج بستر
• موارد لبه مانند رشته های خالی را کنترل نکنید

برنامه های دنیای واقعی
این الگوریتم کاربردهای عملی در:

• تجزیه و تحلیل توالی DNA (توالی palindromic)
• رمزنگاری (تطبیق الگوی)
• فشرده سازی داده ها (یافتن الگوهای مکرر)
• پردازش متن (یافتن ساختارهای آینه ای)
• تشخیص سرقت ادبی (یافتن ساختارهای مشابه)

پایان
رویکرد گسترش مرکز بهترین ترکیب را ارائه می دهد:
🔥 بهینه O (n²) پیچیدگی زمانی
🔥 حداقل O (1) استفاده از فضا
🔥 اجرای تمیز
stronging دست زدن به همه موارد لبه

درک این روش گسترش مرکز به بسیاری از مشکلات دستکاری رشته ای دیگر کمک خواهد کرد. این یک الگوی اساسی است که نشان می دهد چگونه می توانیم با جستجوی تقارن طبیعی در مشکلات ، راه حل های کارآمد پیدا کنیم!