برای دسترسی به سوال 1249 لیت‌کد میتونید از این لینک استفاده کنید. سطح این سوال Medium است.

اگر پیشنهادی برای اصلاح پست دارید، می‌تونید از طریق دکمه‌ی "پیشنهاد اصلاح متن" وارد ریپازیتوری وبلاگ در github بشید و تغییرات مورد نظرتون رو پیشنهاد بدید.

شرایط مسئله

در این مرحله، شرایط خاص مسئله و حالت‌های edge case رو بررسی می‌کنیم. این شرایط باید در توضیحات سوال یا مثال‌ها مشخص شده باشن یا اینکه از پاسخ‌های پیش فرض استفاده کنیم. یک string در چه حالتی معتبره؟ یا خالی باشه یا پرانتزها در اون به شکل درستی باز و بسته شده باشن.

• خروجی الگوریتم چه چیزی باید باشد؟ یک string معتبر که با کمترین تعدادِ حذفِ پرانتزها به دست آمده است.
• اگر چند حالت برای ایجاد string معتبر با کمترین تعدادِ حذفِ پرانتزها وجود داشته باشد چه؟ مثلا فرض کنیم string معتبر نیست، اما با حذف یک پرانتز میتوان آن را به string معتبر تبدیل کرد. اما ممکن است پرانتز دیگری هم وجود داشته باشد که با حذف آن هم بتوان string معتبر دیگری تولید کرد. در این شرایط، برگرداندن یکی از stringهای معتبر کافی است.
• string‌های ورودی فقط شامل “(” و “)” و حروف کوچک انگلیسی هستند.
• آیا یک string خالی، معتبر محسوب می‌شود؟ بله.
• آیا یک string بدون پرانتز، معتبر محسوب می‌شود؟ بله.

نوشتن test case

در این مرحله، چند مثال می‌نویسیم که هم شرایط خواسته شده و هم edge case هایی که بالاتر اشاره کردیم رو pass کنه.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

input = "" 
output = "" 
input = "abcdefg" 
output = "abcdefg" 
input = "a)bc(d)" 
output = "abc(d)" 
input = "(ab(c)a" 
output = "ab(c)a" or "(abc)a" 
input = "))((" 
output = "" 

راه حل منطقی

در این مرحله به دنبال working solution هستیم، یعنی راه حلی منطقی که بتونه مسئله رو حل کنه. به راه حل بهینه فکر نمی‌کنیم. درگیر زبان برنامه نویسی و محدودیت‌های اون هم نخواهیم بود.

برای حل این سوال باید سراغ ساختمان داده‌ی Stack بریم. معمولا در مسائلی که بحث پرانتزهای باز و بسته است، چون نحوه پردازششون باید به صورت LIFO باشه، Stack اهمیت ویژه‌ای پیدا می‌کنه. در Stack، اینکه چگونه داده رو ذخیره و اون رو بازیابی کنیم، مهمه.

یک string در چه حالتی معتبره؟ یا خالی باشه یا پرانتزها در اون به شکل درستی باز و بسته شده باشن. اینکه پیمایش رو از چپ به راست یا از راست به چپ انجام بدیم، تغییری در منطق کار ایجاد نمی‌کنه. بنابراین پیمایش رو از چپ به راست پیش می‌بریم که سر‌راست‌تره. در پیمایشی که خواهیم داشت، سه نوع کاراکتر “)” و “(” و حروف کوچک انگلیسی رو خواهیم دید. حروف کوچک انگلیسی تاثیری روی معتبر بودن یا نبودن string ندارن، پس برامون مهم نخواهند بود. طبق سوال، باید کمترین تعداد ممکنِ پرانتزِ باز یا بسته رو پاک کنیم تا به string معتبر برسیم.

با دیدن یک پرانتزِ باز باید چه کار کنیم؟ ممکنه در ادامه، پرانتزِ بسته‌ی متناظری با اون وجود داشته باشه یا اینکه پرانتزِ بسته‌ی متناظری با اون وجود نداشته باشه که باعث میشه این کاراکتر، یک کاراکتر نامطلوب باشه که باید حذف بشه تا به string معتبر برسیم. در این لحظه چیزی نمی‌دونیم. فقط زمانی که به پایان string رسیده باشیم می‌تونیم در موردش نظر بدیم.

با دیدن یک پرانتزِ بسته باید چه کار کنیم؟ تنها حالتی که یک پرانتزِ بسته می‌تونه در string باقی بمونه و نیازی به حذفش نیست، زمانیه که پرانتز(های) بازی قبل از اون در string وجود داشته باشند، چون این پرانتزِ بسته، می‌تونه یکی از پرانتزهای باز رو بببنده و به معتبر شدن string کمک کنه. البته نیاز نیست بلافاصله بعد از پرانتزِ باز اومده باشه و ممکنه بینشون چند کاراکتر اومده باشه. اگر قبل از پرانتزِ بسته هیچ پرانتزِ بازی وجود نداشته باشه، باید حذفش کنیم.

string زیر رو در نظر بگیرید.

1

(ab(c)d

یک Stack تعریف می‌کنیم. با دیدن هر پرانتزِ باز، index اون رو درون Stack وارد (push) می‌کنیم. با دیدن هر پرانتزِ بسته، از Stack یک خروج (pop) انجام می‌دیم، یعنی رویی‌ترین عنصرش رو خارج می‌کنیم. مثلا در string بالا، با دیدن اولین پرانتزِ باز، Stack به صورت [0] خواهد بود. با دیدن دومین پرانتزِ باز، Stack به صورت [0,3] خواهد بود. با دیدن اولین پرانتزِ بسته، Stack به صورت [0] خواهد بود. به پایان string می‌رسیم. با نگاه به Stack، متوجه می‌شیم که یک کاراکتر پرانتزِ باز در جایگاه 0ام داریم که نامطلوبه و با حذفش، Stack خالی خواهد شد (که به معنای معتبر شدنِ string است). پس باید کاراکترِ در جایگاه 0ام رو پاک کنیم.

string زیر رو در نظر بگیرید.

1

a)bc(d)

یک Stack تعریف می‌کنیم. با دیدن هر پرانتزِ باز، index اون رو درون Stack وارد (push) می‌کنیم. با دیدن هر پرانتزِ بسته، از Stack یک خروج (pop) انجام می‌دیم، یعنی رویی‌ترین عنصرش رو خارج می‌کنیم. مثلا در string بالا، با شروع پیمایش و دیدن اولین پرانتزِ بسته، Stack خالی است. در این حالت چه کنیم؟ چیزی در Stack نیست که بخوایم pop کنیم. بلافاصله اون کاراکتر رو حذف می‌کنیم، چون حتما نامطلوبه. در ادامه پیمایش رو ادامه می‌دیم، یک پرانتزِ باز و یک پرانتزِ بسته داریم که به معنای معتبر بودن string باقی مانده است.

تبدیل راه حل به کد

برای پیاده‌سازی، بهتره string ورودی رو به آرایه تبدیل کنیم، روی آرایه کار کنیم و در نهایت آرایه رو به string تبدیل کنیم و جواب رو برگردونیم. چرا؟ چون در جایی که نیاز به حذفِ درجایِ کاراکتر داریم (در حالتی که Stack خالیه و کاراکتر پرانتزِ بسته دیده‌ایم)، کار با آرایه راحت‌تر از stringه.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public string MinRemoveToMakeValid(string str) 
{
    char[] res = str.ToCharArray();
    Stack < int > stack = Stack < int > ();

    for (int i = 0; i < res.Length; i++) {
      // When I see an open bracket 
      if (res[i] == '(') {
        stack.Push(i);
      }

      // When I see an a close bracket and stack is not empty
      else if (res[i] == ')' && stack.Count > 0) {
        stack.Pop();
      }

      // When I see an a close bracket and stack is empty 
      else if (res[i] == ')') {
        res[i] = '\0'; // Replace '). with null character to mark for removal
      }

      while (stack.Count > 0) {
        int curldx = stack.Pop();
        res[curldx] = '\0'; // Replace remaining '(' with null character 
      }

      // Convert char array to string and remove null characters
      return new string(res).Replace("\O", ""); 
}

پیچیدگی زمانی و حافظه‌ای

در این مرحله به بررسی پیچیدگی زمانی و حافظه ای راه حل می‌پردازیم. یعنی تحلیل می‌کنیم که بین زمان اجرای الگوریتم و حافظه مصرفی آن، چه رابطه ای با اندازه ورودی الگوریتم وجود دارد.

پیچیدگی زمانی الگوریتم O(n) است. n، طول رشته‌ی ورودی است. ابتدا رشته به آرایه تبدیل می‌شود که زمان O(n) می‌گیرد. سپس حلقه‌ای روی عناصر آرایه پیمایش می‌کند که زمان O(n) می‌گیرد و درون هر حلقه، عملیاتی با زمان O(1) انجام می‌شود. مرحله‌ی آخر، تبدیل آرایه به رشته و حذف کاراکترهای null است که نیاز به پیمایش روی همه عناصر آرایه دارد و زمان O(n)  می‌گیرد.

پیچیدگی حافظه‌ای الگوریتم O(n) است. الگوریتم از حافظه با طول n برای ذخیره آرایه استفاده می‌کند و پیچیدگی‌اش O(n) است. در مورد Stack، در بدترین حالت، زمانی که همه پرانتزها باز باشند، Stack بیشترین اندازه خورد را خواهد داشت و پیچیدگی‌اش O(n) خواهد بود.

منابع

udemy