🚀 حل سوال "Find All Anagrams in a String" از LeetCode با تحلیل کامل! 🔍

دو رشته s و p داریم. میخواهیم تمام ایندکسهای شروع آناگرامهای p را در s پیدا کنیم.

📝 مثال:

ورودی: s = "cbaebabacd", p = "abc"
خروجی: [0, 6]
- آناگرام abc در ایندکس 0 (cba) و 6 (bac) وجود دارد.

🧠 رویکرد حل مسئله (Sliding Window Technique)

۱. ایده کلی:

از الگوی sliding window با طول ثابت (برابر طول p) استفاده میکنیم.
فرکانس حروف p را ذخیره کرده و با فرکانس حروف در پنجرههای مختلف s مقایسه میکنیم.

۲. مراحل حل:

آمادهسازی فرکانسها:
- یک آرایه p_count برای ذخیره فرکانس حروف p.
- یک آرایه window_count برای ذخیره فرکانس حروف در پنجره جاری از s.
مقایسه هوشمند:
- با هر حرکت پنجره، فقط حروف جدید اضافه و حروف قدیم حذف میشوند.
- اگر فرکانسها مطابقت داشتند، ایندکس را به جواب اضافه میکنیم.

۳. بهینهسازی:

به جای مقایسه کل آرایهها در هر مرحله، تعداد کاراکترهای منطبق را ردیابی میکنیم (matches).

💻 کد حل مسئله (Python)


def findAnagrams(s: str, p: str) -> list[int]:
    if len(p) > len(s):
        return []
    
    p_count = [0] * 26
    window_count = [0] * 26
    
    # محاسبه فرکانس حروف p و پنجره اولیه s
    for i in range(len(p)):
        p_count[ord(p[i]) - ord('a')] += 1
        window_count[ord(s[i]) - ord('a')] += 1
    
    result = []
    matches = sum(1 for i in range(26) if p_count[i] == window_count[i])
    
    for i in range(len(s) - len(p)):
        if matches == 26:
            result.append(i)
        
        # حذف حرف خروجی از پنجره
        left_char = ord(s[i]) - ord('a')
        window_count[left_char] -= 1
        if window_count[left_char] == p_count[left_char]:
            matches += 1
        elif window_count[left_char] == p_count[left_char] - 1:
            matches -= 1
        
        # اضافه کردن حرف جدید به پنجره
        right_char = ord(s[i + len(p)]) - ord('a')
        window_count[right_char] += 1
        if window_count[right_char] == p_count[right_char]:
            matches += 1
        elif window_count[right_char] == p_count[right_char] + 1:
            matches -= 1
    
    # بررسی آخرین پنجره
    if matches == 26:
        result.append(len(s) - len(p))
    
    return result

📊 تحلیل پیچیدگی

زمانی: ⏱️ O(n)
- هر حرف از s حداکثر دو بار پردازش میشود (ورود و خروج از پنجره).
مکانی: 💾 O(1)
- آرایههای فرکانس اندازه ثابت (26 حرف) دارند.