مسائل پایه رشته
مسائل پایه رشته: معکوس‌سازی، پالیندروم (با دو اشاره‌گر) و آنagram (با شمارش فراوانی)
سه مسئله پایه‌ای
این سه مسئله، آجرهای ساختاری مسائل رشته‌ای‌اند و در مصاحبه‌های مقدماتی پرتکرار:
۱. معکوس‌سازی رشته
با دو اشاره‌گر از دو سر، کاراکترها را جابه‌جا کنید تا به وسط برسند — O(n) و درجا:
def reverse(s):
chars = list(s)
left, right = 0, len(chars) - 1
while left < right:
chars[left], chars[right] = chars[right], chars[left]
left += 1; right -= 1
return "".join(chars)۲. پالیندروم (متن وارونه)
«madam» و «level» وارونه‌اند. با دو اشاره‌گر از دو سر مقایسه کنید — بدون ساخت رشته معکوس!
- نسخه سخت‌گیرانه: فقط حروف و ارقام، بدون بزرگی/کوچکی: «A man, a plan...»
- ترفند: با
isalnum()فیلتر و باlower()یکسان‌سازی کنید
۳. آنagram (هم‌ترکیب)
دو رشته با «کاراکترهای یکسان با فراوانی یکسان»: «listen» و «silent».
سه روش:
| روش | ایده | پیچیدگی |
|---|---|---|
| مرتب‌سازی | sorted(a) == sorted(b) | O(n log n) |
| شمارش فراوانی | آرایه/هش تعداد کاراکترها | O(n) ✓ |
| جمع کد کاراکترها | مجموع/حاصل‌ضرب کدها برابر؟ | O(n) اما نادرست! |
روش سوم را ببینید: «ad» و «bc» جمع کد یکسان اما آنagram نیستند — دام مصاحبه!
گروه‌بندی آنagramها
مسئله کلاسیک: لیست کلمات را گروه‌بندی کنید. کلید هش = رشته مرتب‌شده کلمه! «eat», «tea», «ate» ← کلید «aet».
نکته: برای رشته‌های یونیکد/فارسی، شمارش فراوانی با dict بهتر از آرایه ۲۶تایی انگلیسی است — عمومی‌تر و بدون فرض الفبا.
جمع‌بندی
- معکوس: دو اشاره‌گر به وسط — درجا O(n)
- پالیندروم: مقایسه دو سر بدون ساخت معکوس
- آنagram: شمارش فراوانی O(n) — نه جمع کدها!
- گروه‌بندی آنagram: کلید = رشته مرتب
این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.