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

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

شرایط مسئله

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

• اگه دو تا # (هش) داشته باشیم چی میشه؟ دو کاراکتر قبل از اولین # رو پاک میکنیم.
• اگه کاراکتری وجود نداشته باشه، # چکار میکنه؟ هیچی، وقتی کاراکتری نیست، عملا اتفاقی رخ نمیده.
• آیا دو string خالی یعنی "" و "" با هم برابرند؟ بله، برابرند.
• آیا کوچک و بزرگ بودن حروف مهمه؟ بله، A و a برابر نیستند.

نوشتن test case

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

s = "ab#z", t = "az#z"
output = true
s = "abc#d", t = "acc#c"
output = false
s = "x#y#z#", t = "a#"
output = true
s = "a###b", t = "b"
output = true
s = "Ab#z", t = "ab#z"
output = false

راه حل منطقی

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

بدیهیه که اول باید شکل نهایی هر string رو بدست بیاریم، یعنی ببینیم هر string بعد از تاثیرات #ها چه شکلی خواهد بود. بعدش باید اون‌ها رو مقایسه کنیم تا ببینیم یکسان هستن یا نه. برای این کار از سمت چپ شروع می‌کنیم، هر کاراکتر رو می‌نویسیم، به ازای هر #ای که مشاهده میکنیم، یکی از کاراکترهایی که نوشتیم رو پاک میکنیم (و عملا string جدیدی ساخته میشه). در پایان، ابتدا تعداد کاراکترهای دو string رو مقایسه میکنیم، اگه متفاوت بودن که false برمیگردونیم، اگه برابر بودن، حالت نهایی هر دو string رو با هم مقایسه میکنیم، اگه هر دو string در ایندکس i ام شون کاراکتر یکسانی داشتن (حرف بزرگ و کوچک مهمه) اون موقع true برمیگردونیم و در غیر این صورت با مشاهده اولین تفاوت، باید false برگردونیم.

یک روش حل اینه که در زمان به دست آوردنِ شکل نهاییِ string، اون رو به شکل آرایه ببینیم، مثلا برای “az#z”، آرایه‌ی خالیِ [] رو در نظر می‌گیریم.

اولین حرف، a است. آیا # است؟ خیر. پس اون رو به آرایه اضافه می‌کنیم و داریم [a].

دومین حرف، z است. آیا # است؟ خیر. پس اون رو به آرایه اضافه می‌کنیم و داریم [a,z].

سومین حرف، # است. آیا # است؟ بله. پس آخرین عضو آرایه رو حذف می‌کنیم و داریم [a].

چهارمین حرف، z است. آیا # است؟ خیر. پس اون رو به آرایه اضافه می‌کنیم و داریم [a,z].

پس آرایه‌ی نهایی به صورت [a,z] خواهد بود.

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

 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

public bool BackspaceCompare(string S, string T) {
  List < char > finalS = BuildString(S);
  List < char > finalT = BuildString(T);

  if (finalS.Count != finalT.Count) {
    return false;
  }
  else {
    for (int p = 0; p < finalS.Count; p++) {
      if (finalS[p] != finalT[p]) {
        return false;
      }
    }
  }
  return true;
}

private List < char > BuildString(string input) {
  List < char > builtString = new List < char > ();
  foreach(char c in input) {
    if (c != '#') {
      builtString.Add(c);
    } else if (builtString.Count > 0) {
      builtString.RemoveAt(builtString.Count - 1);
    }
  }
  return builtString;
}

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

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

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

تابع BackSpaceCompare که وظیفه‌ی بررسی یکسان بودن stringها رو بر عهده داره، دو ورودی S با اندازه‌ی s و T با اندازه‌ی t داره. در بدترین حالت، پیچیدگی این تابع، با توجه به اینکه تابع BuildString رو هم فراخوانی می‌کنه و اون هم از مرتبه‌ی O(s) یا O(t) خواهد بود، از مرتبه‌ی (2s+t) یا (2t+s) خواهد بود که با نادیده گرفتن ضرایب، به شکل O(s+t) درمیاد.

در مورد پیچیدگی حافظه‌ای هم به همین شکل میشه استدلال کرد. بنابراین پیچیدگی زمانی و پیچیدگی حافظه‌ای هر دو O(s+t) است.

بهینه‌سازی

پیچیدگی زمانی O(s+t) است و بهتر نمیشه! اما در مورد پیچیدگی حافظه‌ای میشه کارهایی برای بهبود انجام داد.

در مورد پیچیدگی حافظه‌ای، در الگوریتمی که داریم، در بدترین حالت، آرایه‌هایی با طول s و t خواهیم داشت، چون در بدترین حالت، هیچ #ای وجود ندارد و تمام حروف را به آرایه اضافه خواهیم کرد. سوال در نهایت از ما true/false می‌خواد. اون آرایه‌هایی که می‌سازیم صرفا برای راحت‌تر کردن کار خودمونه و خواسته‌ی مستقیمِ سوال نیست. دو رشته‌‌ی زیر رو در نظر بگیرید.

1
2

S = "abc#d"
T = "abzz##d"

فرض کنید قراره از تکنیک two pointers استفاده کنیم. P1 رو روی اولین حرف S از چپ و P2 رو روی اولین حرف T از چپ قرار میدیم. از چپ به راست شروع به حرکت میکنیم. مشکل زمانی پیش میاد که حروف در ظاهر یکسان نیست و الگوریتم به اشتباه false برخواهد گردوند. مثلا در مورد حرف سوم، P1 روی ‘c’ و P2 روی ‘z’ است، اما میدونیم که این حروف، حذف خواهند شد.

در این سوال خاص، حرکت از چپ به راست با حرکت از راست به چپ تفاوت داره. چون عملا قوانین زبان و کاراکتر # که نقش Backspace رو بازی می‌کنه، در اون حاکم است. ما تا زمانی که #(ها) رو ندیده‌ایم، نمیتونیم با اطمینان بگیم که اون حرفی که الان پوینتر روش قرار داره، باقی خواهد ماند یا حذف خواهد شد.

پس حرکت رو از راست به چپ پیش می‌بریم تا ابتدا #(ها) رو ببینیم. P1 رو روی اولین حرف S از راست و P2 رو روی اولین حرف T از راست قرار میدیم. از راست به چپ شروع به حرکت میکنیم. اگه اولین حروف یکسان باشن، مطمئنیم که مشکلی وجود نخواهد داشت، چون در سمت راستِ اونها، کاراکتری وجود نداره (اگر وجود داشت، ممکن بود # باشه و باعث حذفشون بشه).

خب، حالا اگه پوینتر روی # قرار بگیره چی؟ مثلا P1 در رشته‌ی S روی # قرار بگیره. اولین ایده اینه که هر وقت # دیدیم، به جای 1 خانه، 2 خانه جلو بریم و عملا ‘c’ رو نادیده بگیریم. اگر فقط یک # داشته باشیم، این ایده خوب کار میکنه، اما اگر چند # کنار هم باشن، نتیجه غلط خواهد بود، مثل رشته‌ی T. پس باید پوینترها، نوعی حافظه داشته باشن، تا حواسشون باشه که چند تا # دیده‎‌اند.

مثلا فرض کنیم پوینتر روی اولین # (از راست) در رشته‌ی T قرار داره.  الان میدونه که باید 2 خانه جلو بره. اما 2 خانه جلو نمیره، بلکه 1 خانه میره تا ببینه حرف بعدی چیه، طیِ این حرکت کردن، 1 واحد از خانه‌هایی که باید جلو بره کم میشه.

الان روی دومین # (از راست) قرار داره. حرفی که دیده، باز هم # است. پس میدونه که باید 2 خانه جلو بره، از قبل هم باید 1 خانه جلو می‌رفت. پس مجموعا باید 3 خانه جلو بره. اما 3 خانه جلو نمیره، بلکه 1 خانه میره تا ببینه حرف بعدی چیه. طیِ این حرکت کردن، 1 واحد از خانه‌هایی که باید جلو بره کم میشه.

الان روی اولین z (از راست) قرار داره. حرفِ غیرِ # دیده. از قبل باید 2 خانه جلو می‌رفت. اما 2 خانه جلو نمیره، بلکه 1 خانه میره تا ببینه حرف بعدی چیه. طیِ این حرکت کردن، 1 واحد از خانه‌هایی که باید جلو بره کم میشه.

الان روی دومین z (از راست) قرار داره. حرفِ غیرِ # دیده. از قبل باید 1 خانه جلو می‌رفت. همون 1 خانه رو جلو میره تا ببینه حرف بعدی چیه. روی b قرار می‌گیره. در ادامه، یا حرفِ غیرِ # می‌بینه که عادی جلو میره، یا # می‌بینه که روش بالا رو تکرار می‌کنه.

 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

public class Solution {
    public bool BackspaceCompare(string s, string t) {
        int p1 = s.Length - 1, p2 = t.Length - 1;

            while (p1 >= 0 || p2 >= 0)
            {
                if (p1 >= 0 && s[p1] == '#' || p2 >= 0 && t[p2] == '#')
                {
                    if (p1 >= 0 && s[p1] == '#')
                    {
                        int backCount = 2;

                        while (backCount > 0)
                        {
                            p1--;
                            backCount--;

                            if (p1 >= 0 && s[p1] == '#')
                            {
                                backCount += 2;
                            }
                        }
                    }

                    if (p2 >= 0 && t[p2] == '#')
                    {
                        int backCount = 2;

                        while (backCount > 0)
                        {
                            p2--;
                            backCount--;

                            if (p2 >= 0 && t[p2] == '#')
                            {
                                backCount += 2;
                            }
                        }
                    }
                }
                else
                {
                    if (p1 >= 0 && p2 >= 0 && s[p1] != t[p2])
                    {
                        return false;
                    }
                    else
                    {
                        p1--;
                        p2--;
                    }
                }
            }

            return true;
    }
}

پیچیدگی زمانی، مشابه با راه حل قبلی، O(s+t) است، اما پیچیدگی حافظه‌ای به O(1) رسیده است.

منابع

udemy