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

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

شرایط مسئله

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

• اگر string ورودی خالی (empty) باشد، true برمی‌گردانیم.

نوشتن test case

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

input = "[{()}]"
output = true
input = "{([)]}"
output = false
input = "{([]"
output = true
input = ""
output = true
input = "{()[]}"
output = true

راه حل منطقی

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

طبق صورت سوال، تعدادی پرانتز باز به شکل های ) و } و ] داریم و تعدادی پرانتز بسته به شکل های ( و { و [. عبارتی شامل این کاراکترها به ما داده شده، میخواهیم چک کنیم که پرانتزگذاری معتبر است یا نه. معتبر بودن به چه معناست؟ یعنی هر پرانتزی که باز می‌شود، بسته شود. هم تعداد پرانتزهای باز و بسته باید مطابق هم باشد و هم جایگاهشان، یعنی پرانتزهای نزدیک با هم و پرانتزهای دور با هم تطابق داشته باشند. نوع ورودی سوال ما را به یاد ساختمان داده Stack می‌اندازد. چرا سراغ ساختمان داده Stack می‌ریم؟

معتبر بودن یا نبودن string ورودی رو چه چیزی تعیین می‌کنه؟ ما دو نوع پرانتز داریم، باز و بسته. هر کدوم از این‌ها، سه نوع نمایش دارن. بازها ) و } و ] هستن و بسته‌ها ( و { و [. ما پیمایش string رو از چپ به راست یا از راست به چپ انجام می‌دیم. فرض کنیم قراره از چپ به راست بریم. وقتی یک پرانتز باز می‌بینیم، آیا می‌دونیم که پرانتزِ بسته‌ی متناظر با اون هم وجود داره یا نه؟ نه، نمیدونیم، چون ممکنه چند پرانتز باز دیگه هم در ادامه وجود داشته باشن. پس فقط وقتی به انتهای string برسیم می‌تونیم بگیم معتبر است، اما غیر معتبر بودنش ممکنه سریع‌تر مشخص بشه.

وقتی یک پرانتز بسته می‌بینیم، می‌دونیم که پرانتز بازی از همون نوع وجود داشته، اما کجا وجود داشته؟ دقیقا قبل از همون پرانتزِ بسته. نمی‌تونه مثلا 2 یا 3 کاراکتر قبل باشه. این نوع نگاه به مسئله، دقیقا همون کاریه که Stack انجام میده. پشته بر اساس LIFO کار می‌کنه. در پشته عمل اضافه کردن و حذف عنصر، فقط در یک طرف آن، بنام بالای پشته انجام می‌شه، یعنی عنصری که از همه دیرتر وارد پشته شد، از همه زودتر از پشته حذف می‌شه.

مثل گذاشتن چند بشقاب روی هم. اولین بشقاب رو روی میز می‌ذاریم، دومین بشقاب روی اولین بشقاب قرار می‌گیره. سومین بشقاب روی دومین بشقاب قرار می‌گیره. حالا می‌خوایم اونها رو برداریم. نمیشه بشقاب های زیرین رو برداشت. ابتدا باید رویی‌ترین بشقاب رو برداریم، در واقع سومین بشقابیه که گذاشتیم. دوباره، باید رویی‌ترین بشقاب رو برداریم، در واقع دومین بشقابیه که گذاشتیم. در انتها باز هم باید باید رویی‌ترین بشقاب رو برداریم، در واقع اولین بشقابیه که گذاشتیم. به این نوع گذاشتن و برداشتن می‌گن LIFO.

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

اگه طول رشته 0 باشه، true برمی‌گردونیم. روی تک تک کاراکترها جلو می‌ریم. اگه key‌های دیکشنری که همون پرانتزهای باز هستن رو ببینیم، اون رو به استک اضافه می‌کنیم. در غیر این صورت وارد else می‌شیم. حالا ما یک پرانتزِ بسته دیده‌ایم. رویی‌ترین عنصر موجود در استک رو که یک پرانتز باز هست در متغیر leftBracket نگه می‌داریم. پرانتزِ بسته‌ی متناظر با اون رو در متغیر correctBracket نگه می‌داریم (قبلا پرانتزهای باز و پرانتزِ بسته‌ی متناظرشون رو در دیکشنری ذخیره کرده بودیم). حالا چک می‌کنیم که این پرانتزِ بسته‌ای که در string دیده‌ایم، همون چیزی هست که باید باشه یا نه. اگه نباشه false برمی‌گردونیم و تمام. اگه باشه، حلقه ادامه پیدا می‌کنه. هر جا که پرانتزِ بسته‌ای خلاف انتظار ما وجود داشته باشه، حلقه تموم میشه، در غیر این صورت به انتهای string می‌رسیم.

انتظار داریم در پایان، به ازای هر پرانتزِ بازی که دیده بودیم (و در استک push کردیم)، پرانتزِ بسته‌ای دیده باشیم (و پرانتزِ باز متناظر با اون رو از استک pop کرده باشیم)، بنابراین نباید چیزی توی استک مونده باشه.

 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
30
31

public bool IsValid(string s)
{
  if (s.Length == 0) return true;

  Dictionary<char, char> parens = new Dictionary<char, char> {
    {'(', ')'},
    {'{', '}'},
    {'[', ']'}
  };

  Stack<char> stack = Stack<char>();

  for (int i = 0; i < s.Length; i++)
  {
    // when I see a left bracket 
    if (parens.ContainsKey(s[i])) {
      stack.Push(s[i]);
    }
    // when I see a right bracket 
    else {
      if (stack.Count == 0) return false;

      char leftBracket = stack.Pop();
      char correctBracket = parens[leftBracket];

      (s[i] != correctBracket) return false;

    }
  }
  return stack.Count == 0;
}

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

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

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

منابع

udemy