سلام دوستان عزیز، من مهدی شاملو هستم و در این پست میخوام روش حل سوال سوم LeetCode رو که یکی از سوالات کلاسیک و جالب در سطح Medium هست، به اشتراک بذارم.
البته مثل همیشه باید بگم که هر سوالی رو میتونید به روشهای مختلفی حل کنید و فقط یک راه درست وجود نداره، اما این راهحلی هست که خودم پیادهسازی کردم و امیدوارم براتون مفید باشه!
صورت سوال: Longest Substring Without Repeating Characters
باید طول بلندترین زیررشته (substring) رو پیدا کنیم که هیچ کاراکتر تکراری نداشته باشه.
مثال:
Input: s = "abcabcbb" Output: 3
Input: s = "bbbbb" Output: 1
Input: s = "pwwkew" Output: 3
محدودیتها: طول رشته تا ۵*۱۰^۴ و شامل حروف انگلیسی، اعداد، سمبلها و فضای خالی.
راهحل من (رویکرد ساده با دو حلقه تو در تو)
من از یک رویکرد ساده استفاده کردم که همه زیررشتههای ممکن رو بررسی میکنه و طول بلندترین اونهایی که تکرار ندارن رو نگه میداره.
برای این کار، یک لیست موقت برای نگهداری کاراکترهای فعلی استفاده کردم و هر بار که تکرار دیدم، لیست رو ریست کردم.
class Solution(object): def lengthOfLongestSubstring(self, s): max_len = 0 lists = [] for i in range(0, len(s)): for z in range(i, len(s)): if s[z] in lists: lists = [] break else: lists.append(s[z]) if max_len < len(lists): max_len = len(lists) return max_len
توضیح گام به گام:
۱. یک متغیر max_len برای نگهداری حداکثر طول اولیه صفر میذاریم.
۲. با یک حلقه خارجی از هر اندیس i به عنوان شروع زیررشته شروع میکنیم.
۳. با حلقه داخلی از i تا آخر رشته، کاراکترها رو یکی یکی اضافه میکنیم.
۴. اگر کاراکتر تکراری دیدیم، لیست موقت رو خالی میکنیم و حلقه داخلی رو میشکنیم (یعنی زیررشته جدید از جای بعدی شروع میشه).
۵. بعد از هر زیررشته، طولش رو با max_len مقایسه میکنیم و اگر بزرگتر بود، آپدیت میکنیم.
این روش ساده و قابل فهمه، اما پیچیدگی زمانیاش O(n²) هست که برای رشتههای خیلی بلند ممکنه کند باشه (هرچند با محدودیت LeetCode پاس میشه).
اگر راهحل بهتری دارید (مثلاً با تکنیک Sliding Window که O(n) هست و خیلی بهینهتره)، خوشحال میشم داخل کامنتها یا گیتهابم بهم بگید تا کدم رو بهبود بدم!
اگر سوالی داشتید یا نیاز به توضیح بیشتر بود، بپرسید که اگر بلد بودم کمک کنم
نویسنده: مهدی شاملو | Mahdi Shamlou
