حل سوال استخدامی برنامه نویسی پایتون قسمت پنجم با علی برادر خدام خسروشاهی

LeetCode75

345. Reverse Vowels of a String

Given a string s, reverse only all the vowels in the string and return it.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

Example 1:

Input: s = "IceCreAm"

Output: "AceCreIm"

Explanation:

The vowels in s are ['I', 'e', 'e', 'A']. On reversing the vowels, s becomes "AceCreIm".

Example 2:

Input: s = "leetcode"

Output: "leotcede"

Constraints:

• 1 <= s.length <= 3 * 105
• s consist of printable ASCII characters.

📌 تحلیل و فهم مسئله

ما یه رشته s داریم و باید فقط حروف صدادار (vowels) داخلش رو برعکس کنیم، در حالی که بقیه حروف همون‌جوری باقی بمونن.

🔠 حروف صدادار:
حروف صدادار در زبان انگلیسی این‌ها هستن:

• 'a', 'e', 'i', 'o', 'u'
• هم حروف کوچک (aeiou) و هم حروف بزرگ (AEIOU) جزو صدادارها حساب می‌شن.

📌 چطور الگوریتمش رو بفهمیم؟

برای حل این مسئله باید فقط جای حروف صدادار رو عوض کنیم.
پس بهتره از یه روش استفاده کنیم که بدون جابه‌جایی غیرضروری، فقط صدادارها رو تغییر بده.

✍️ مراحل حل مسئله

1. پیدا کردن همه‌ی حروف صدادار در رشته و ذخیره‌ی اون‌هایه لیست (vowels) درست می‌کنیم که فقط حروف صدادار s رو نگه داره.
   اون‌ها رو به ترتیب معکوس برمی‌گردونیم.
   
2. حلقه‌ی دوم برای جایگزین کردن صدادارهایه لیست قابل تغییر از s می‌سازیم.
   وقتی به یه حرف صدادار رسیدیم، از لیست vowels مقدار جدید رو برمی‌داریم و جایگزین می‌کنیم.
   

📌 کد پایتون (با کلاس Solution):

class Solution:

def reverseVowels(self, s: str) -> str:

vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}

# چون رشته‌ها تغییرناپذیر هستن، تبدیل به لیست می‌کنیم

s = list(s)

# دو اشاره‌گر برای حرکت از ابتدا و انتها

left, right = 0, len(s) - 1

while left < right:

# حرکت به سمت راست تا وقتی که به صدادار برسیم

while left < right and s[left] not in vowels:

left += 1

# حرکت به سمت چپ تا وقتی که به صدادار برسیم

while left < right and s[right] not in vowels:

right -= 1

# اگر هنوز اشاره‌گرها عبور نکردن، جابه‌جا کنیم

if left < right:

s[left], s[right] = s[right], s[left]

left += 1

right -= 1

# تبدیل لیست به رشته

return ''.join(s)

#علی برادر خدام خسروشاهی

تصویر با کیفیت کد:

https://khatamnovin.alikayh.workers.dev/download/BQACAgQAAxkDAAMOZ8rf_ynYoqHzZcpNmCBH-CGzapsAApwZAAJSkVlSkl2ETTsSikw2BA/documents/file_19.png

📌 توضیح مرحله‌به‌مرحله کد

1. تعریف vowelsیه مجموعه (set) از حروف صدادار (کوچک و بزرگ) ایجاد کردیم.
   استفاده از set باعث می‌شه که چک کردن یه حرف خیلی سریع باشه (O(1)).
   
2. تبدیل رشته به لیست رشته‌ها (str) قابل تغییر نیستن، پس اونا رو به لیست (list) تبدیل می‌کنیم تا بتونیم جایگزین کنیم.
   
3. دو اشاره‌گر (left و right)left از اول رشته شروع می‌کنه.
   right از انتهای رشته شروع می‌کنه.
   هدف اینه که حروف صدادار رو از ابتدا و انتها پیدا کنیم و جایگزین کنیم.
   
4. حلقه‌ی while برای جابه‌جایی حروف صداداراگر s[left] صدادار نبود، به جلو حرکت کن (left += 1)
   اگر s[right] صدادار نبود، به عقب حرکت کن (right -= 1)
   وقتی دو تا صدادار پیدا شد، جابه‌جا کن.
   
5. برگرداندن لیست به رشته در نهایت ''.join(s) می‌زنیم تا لیست رو به رشته برگردونیم.
   

📌 تحلیل زمانی و کارایی

✅ پیچیدگی زمانی (O(n))

• چون فقط یه بار روی s حرکت می‌کنیم و در هر مرحله یکی از دو اشاره‌گر (left و right) جلو میره، حداکثر O(n) اجرا داره.

✅ پیچیدگی فضایی (O(n))

• چون یک لیست کمکی برای s ساختیم، به اندازه O(n) فضا نیاز داریم.

✅ راه‌حل سریع و بهینه

• این روش نسبت به ذخیره و معکوس کردن مستقیم حروف صدادار بهتر و سریع‌تره، چون تعداد جابه‌جایی‌ها کمتره.

📌 نتیجه‌گیری

✅ ما یاد گرفتیم که چطور فقط حروف صدادار رو معکوس کنیم، بدون اینکه تغییری در بقیه رشته بدیم.
✅ از دو اشاره‌گر (two pointers) استفاده کردیم که سرعت رو بهبود بخشید.
✅ روش ما هم کارآمد (O(n)) و هم ساده بود و به راحتی روی رشته‌های طولانی هم اجرا می‌شه. 🚀😊

علی برادر خدام خسروشاهی