در این مطلب، ویدئو رمزگشایی رشته – Leetcode 394 – Python با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:16:25
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,080 –> 00:00:01,920
سلام به همه خوش آمدید و بیایید امروز
2
00:00:01,920 –> 00:00:04,160
چند کد دقیق تر بنویسیم، بنابراین امروز
3
00:00:04,160 –> 00:00:06,960
بیایید مشکل رشته رمزگشایی را حل کنیم،
4
00:00:06,960 –> 00:00:08,639
این با
5
00:00:08,639 –> 00:00:10,880
مشکل اخیری که حل کردیم که در رشته کد
6
00:00:10,880 –> 00:00:12,639
و رمزگشایی بود، متفاوت است، این یک
7
00:00:12,639 –> 00:00:14,639
مشکل بسیار متفاوت است، هرچند که تقریباً این مشکل را دارد
8
00:00:14,639 –> 00:00:16,640
. دقیقاً همان نام، بنابراین در
9
00:00:16,640 –> 00:00:20,240
این مورد به ما یک رشته رمزگذاری شده
10
00:00:20,240 –> 00:00:22,560
بر اساس قوانین خاصی داده می شود و می خواهیم
11
00:00:22,560 –> 00:00:26,000
رشته رمزگشایی شده را برگردانیم، بنابراین
12
00:00:26,000 –> 00:00:28,960
قانون اصلی در اینجا این است که می توانیم
13
00:00:28,960 –> 00:00:31,519
متنی داشته باشیم که اساساً با این
14
00:00:31,519 –> 00:00:34,399
الگوی کوچک در اینجا مطابقت داشته باشد k اساساً k
15
00:00:34,399 –> 00:00:36,000
است. یک عدد صحیح را نشان می دهیم و
16
00:00:36,000 –> 00:00:38,239
سپس تعدادی براکت خواهیم داشت
17
00:00:38,239 –> 00:00:40,160
و این براکت ها حاوی
18
00:00:40,160 –> 00:00:43,200
تعدادی کاراکتر هستند، به عنوان مثال می
19
00:00:43,200 –> 00:00:45,440
توانیم چیزی شبیه به اینجا داشته
20
00:00:45,440 –> 00:00:48,719
باشیم که در سمت راست می بینید ما یک دو را می بینیم و سپس یک b c را می بینیم که
21
00:00:48,719 –> 00:00:51,440
اساساً به چه معناست. این است که این
22
00:00:51,440 –> 00:00:54,160
عدد صحیح در اینجا، در این مورد دو
23
00:00:54,160 –> 00:00:55,680
نشاندهنده چند بار
24
00:00:55,680 –> 00:00:57,920
25
00:00:57,920 –> 00:00:59,760
این است که این رشته را که در داخل
26
00:00:59,760 –> 00:01:02,079
براکتها قرار دارد، این ورودی را تکرار کنیم، بنابراین چگونه یک رشته را جایگزین کنیم.
27
00:01:02,079 –> 00:01:04,239
مانند این، ما آن را با
28
00:01:04,239 –> 00:01:08,000
دو قبل از میلاد متوالی جایگزین میکنیم، بنابراین میتوانیم bc و bc را دریافت کنیم،
29
00:01:08,000 –> 00:01:10,640
البته اگر سه قبل از
30
00:01:10,640 –> 00:01:13,600
میلاد در اینجا داشتیم، پس میتوانیم یک چیزی شبیه به این سه قبل از میلاد را دریافت کنیم،
31
00:01:13,600 –> 00:01:17,119
بنابراین این قانون کلی است،
32
00:01:17,119 –> 00:01:19,200
بنابراین خیلی ساده به نظر میرسد.
33
00:01:19,200 –> 00:01:21,360
با توجه به رشتهای مانند این، البته میتوانیم
34
00:01:21,360 –> 00:01:24,560
آن را به درستی رمزگشایی کنیم، ما سه a
35
00:01:24,560 –> 00:01:26,400
داریم، سه عدد a در
36
00:01:26,400 –> 00:01:28,560
ابتدا میگیریم، سپس دو bc داریم، سپس
37
00:01:28,560 –> 00:01:32,000
یک bc و یک bc خواهیم داشت و سپس میتوانید
38
00:01:32,000 –> 00:01:34,479
ببینید که این رشته برابر است
39
00:01:34,479 –> 00:01:37,439
خروجی مورد انتظار چه خواهد بود، اما
40
00:01:37,439 –> 00:01:39,040
مشکل این مشکل این است
41
00:01:39,040 –> 00:01:42,399
که این براکت ها در واقع می توانند
42
00:01:42,399 –> 00:01:44,799
43
00:01:44,799 –> 00:01:46,240
44
00:01:46,240 –> 00:01:48,640
45
00:01:48,640 –> 00:01:50,399
46
00:01:50,399 –> 00:01:51,680
تودرتو شوند.
47
00:01:51,680 –> 00:01:53,119
معتبر باشد، بنابراین همیشه یک
48
00:01:53,119 –> 00:01:55,520
عدد صحیح قبل از برخی از براکت ها وجود خواهد داشت و
49
00:01:55,520 –> 00:01:57,200
براکت ها همیشه حاوی
50
00:01:57,200 –> 00:02:00,000
تعدادی کاراکتر در داخل آن هستند، اما
51
00:02:00,000 –> 00:02:02,479
می توان آن را شبیه به مثال دوم تودرتو کرد،
52
00:02:02,479 –> 00:02:04,479
ما می توانیم پرانتز و
53
00:02:04,479 –> 00:02:07,040
th داشته باشیم. en میتوانیم مقداری رشته درست و
54
00:02:07,040 –> 00:02:08,959
سپس یک 2 داشته باشیم، زیرا این 2
55
00:02:08,959 –> 00:02:12,080
متعلق به جفت براکتهای بعدی
56
00:02:12,080 –> 00:02:14,720
مانند این است، پس چگونه میتوان
57
00:02:14,720 –> 00:02:16,959
رشتهای مانند این را رمزگشایی کرد و بیایید در
58
00:02:16,959 –> 00:02:18,720
واقع 3 را در ابتدا اضافه کنیم، پس این چه کار میکند
59
00:02:18,720 –> 00:02:21,680
به ما بگویید این به ما می گوید 3 این 3
60
00:02:21,680 –> 00:02:24,480
برای همه چیزهایی که در داخل این
61
00:02:24,480 –> 00:02:26,720
براکت ها قرار دارد صدق می کند، بنابراین می خواهیم
62
00:02:26,720 –> 00:02:29,200
این رشته را سه بار ضرب کنیم چگونه
63
00:02:29,200 –> 00:02:31,280
این رشته را خوب بفهمیم، باید
64
00:02:31,280 –> 00:02:33,280
با اولین کاراکتر a شروع کنیم و سپس
65
00:02:33,280 –> 00:02:36,000
به دو می رسیم که متعلق به این براکت است، بنابراین
66
00:02:36,000 –> 00:02:38,480
می توانید ببینید که ما یک مشکل فرعی
67
00:02:38,480 –> 00:02:41,040
در داخل مشکل اصلی داریم، بنابراین می
68
00:02:41,040 –> 00:02:43,120
توانید فکر کنید که این مشکل ممکن است
69
00:02:43,120 –> 00:02:45,360
خود را به نوعی راه حل بازگشتی برساند،
70
00:02:45,360 –> 00:02:47,840
بنابراین اکنون که وارد این دو شدیم،
71
00:02:47,840 –> 00:02:50,720
این دو اساساً
72
00:02:50,720 –> 00:02:52,319
این را نشان می دهند. سپس ما
73
00:02:52,319 –> 00:02:54,160
داخل این براکت را بررسی می کنیم،
74
00:02:54,160 –> 00:02:56,080
می بینیم که همه چیز در
75
00:02:56,080 –> 00:02:58,560
اینجا خوب است، یک c ما به
76
00:02:58,560 –> 00:03:00,000
براکت بسته می شویم، این بدان معناست که ما با
77
00:03:00,000 –> 00:03:02,080
این مشکل فرعی به پایان رسیده ایم، این به c ارزیابی می شود
78
00:03:02,080 –> 00:03:02,959
79
00:03:02,959 –> 00:03:05,760
اما این c باید دو بار ضرب شود،
80
00:03:05,760 –> 00:03:07,760
بنابراین ما دو
81
00:03:07,760 –> 00:03:09,280
یا اساساً c
82
00:03:09,280 –> 00:03:11,360
c را می گیریم و این دو به درستی انجام می شود،
83
00:03:11,360 –> 00:03:12,959
ما با آن دو کار کردیم و البته
84
00:03:12,959 –> 00:03:14,720
در ابتدا
85
00:03:14,720 –> 00:03:16,480
کاراکتر کوچک a را داشتیم، بنابراین
86
00:03:16,480 –> 00:03:19,360
اکنون مشکل این است.
87
00:03:19,360 –> 00:03:21,599
دقیقاً به این uh تغییر یافته است بنابراین در داخل
88
00:03:21,599 –> 00:03:23,440
براکت ها یک c c
89
00:03:23,440 –> 00:03:25,599
داریم که می توانیم آن را سه بار ضرب
90
00:03:25,599 –> 00:03:28,400
کنیم و فقط آن نوع رشته را
91
00:03:28,400 –> 00:03:29,840
سه بار دریافت می کنیم.
92
00:03:29,840 –> 00:03:32,480
93
00:03:32,480 –> 00:03:35,519
94
00:03:35,519 –> 00:03:38,000
برای اینکه تنها منطق پیچیده ای
95
00:03:38,000 –> 00:03:40,000
در این مشکل باشد و چند
96
00:03:40,000 –> 00:03:42,239
راه حل برای حل آن وجود دارد، بنابراین بیایید
97
00:03:42,239 –> 00:03:44,000
به آن بپردازیم و سپس می توانیم وارد کد شویم،
98
00:03:44,000 –> 00:03:46,959
بنابراین همانطور که گفتم، براکت های تو در تو
99
00:03:46,959 –> 00:03:49,040
چیست که این
100
00:03:49,040 –> 00:03:51,360
مشکل را دشوار می کند. شما می توانید فکر کنید که
101
00:03:51,360 –> 00:03:53,200
یک راه ممکن که بتوانیم براکت های تودرتو داشته باشیم
102
00:03:53,200 –> 00:03:55,120
این است که می دانید چند براکت بیرونی داریم
103
00:03:55,120 –> 00:03:57,439
و سپس در داخل آن ها
104
00:03:57,439 –> 00:03:59,840
یک براکت تودرتو داریم و سپس
105
00:03:59,840 –> 00:04:01,280
در داخل آن یک
106
00:04:01,280 –> 00:04:04,000
براکت تودرتو داریم. اگر درخت تصمیم
107
00:04:04,000 –> 00:04:05,920
یا درخت مشکل فرعی به نظر
108
00:04:05,920 –> 00:04:07,439
خوب می رسد، البته می دانید که ما
109
00:04:07,439 –> 00:04:09,760
براکت های بیرونی اصلی
110
00:04:09,760 –> 00:04:11,599
را در خارج خواهیم داشت و سپس در داخل آن
111
00:04:11,599 –> 00:04:13,519
، یک مشکل فرعی
112
00:04:13,519 –> 00:04:15,439
دیگر و سایر براکت های تو در تو و سپس
113
00:04:15,439 –> 00:04:17,680
براکت های تو در تو دیگری خواهیم داشت تا
114
00:04:17,680 –> 00:04:20,160
حل شود. این مشکل بیرونی ابتدا باید
115
00:04:20,160 –> 00:04:22,639
این مشکل را حل کنیم و
116
00:04:22,639 –> 00:04:25,440
برای حل این مشکل باید
117
00:04:25,440 –> 00:04:27,360
مشکل فرعی بعدی uh را در اینجا
118
00:04:27,360 –> 00:04:29,680
حل کنیم، پس وقتی این مشکل را حل کردیم، میتوانیم از آن
119
00:04:29,680 –> 00:04:31,919
نسخه پشتیبان تهیه کنیم، میدانید که احتمالاً به
120
00:04:31,919 –> 00:04:34,320
صورت بازگشتی یک مشکل است. روش معتبر
121
00:04:34,320 –> 00:04:36,080
برای حل این مشکل ما میتوانیم
122
00:04:36,080 –> 00:04:38,240
به اینجا برگردیم تا آن مشکل را حل کنیم و
123
00:04:38,240 –> 00:04:40,720
سپس میتوانیم به ریشه برگردیم
124
00:04:40,720 –> 00:04:43,120
و آن مشکل را حل کنیم، بنابراین یک
125
00:04:43,120 –> 00:04:45,120
راهحل بازگشتی اولین
126
00:04:45,120 –> 00:04:47,120
راه بصری است که من واقعاً برای حل آن فکر میکنم.
127
00:04:47,120 –> 00:04:48,240
این مشکل البته ما میتوانیم
128
00:04:48,240 –> 00:04:49,840
ساختار تودرتوی متفاوتی داشته
129
00:04:49,840 –> 00:04:51,680
باشیم، چیزی شبیه به این، بنابراین میدانید که
130
00:04:51,680 –> 00:04:54,160
ما براکتهای بیرونی را داریم
131
00:04:54,160 –> 00:04:57,040
درست این یک راه ممکن
132
00:04:57,040 –> 00:04:59,040
است و سپس در داخل آن تک
133
00:04:59,040 –> 00:05:02,080
براکت سه تا داریم. براکت های تو در تو متفاوت،
134
00:05:02,080 –> 00:05:04,639
بنابراین می دانید
135
00:05:04,639 –> 00:05:07,600
درخت تصمیم بازگشتی ما ممکن است چیزی شبیه به این به نظر برسد،
136
00:05:07,600 –> 00:05:09,360
137
00:05:09,360 –> 00:05:11,840
در این مورد که
138
00:05:11,840 –> 00:05:13,759
ما سه گره فرزند داریم، بنابراین شما می دانید که برای
139
00:05:13,759 –> 00:05:16,000
حل این مشکل بیرونی ابتدا باید
140
00:05:16,000 –> 00:05:18,720
این مشکل را حل کنیم و سپس
141
00:05:18,720 –> 00:05:20,320
باید این مشکل را حل کنیم و سپس
142
00:05:20,320 –> 00:05:22,400
باید این مشکل را حل کنیم و بعد از اینکه
143
00:05:22,400 –> 00:05:23,759
هر سه مورد را حل کردیم،
144
00:05:23,759 –> 00:05:26,560
میتوانیم پشتیبانگیری کنیم و سپس این یکی را
145
00:05:26,560 –> 00:05:29,039
بهطور شهودی انجام دهیم که بتوانیم به صورت بازگشتی
146
00:05:29,039 –> 00:05:31,280
این مشکل را حل کنیم و ما واقعاً نمیتوانیم از آنجایی
147
00:05:31,280 –> 00:05:32,960
که این کار را به صورت بازگشتی انجام میدهیم، اگر این کار را
148
00:05:32,960 –> 00:05:34,479
انجام میدهیم، مجبور نیستیم
149
00:05:34,479 –> 00:05:36,160
مانند یک پشته نگهداری کنیم، به حافظه اضافی نیاز نداریم
150
00:05:36,160 –> 00:05:37,919
زیرا پشته تماس بازگشتی
151
00:05:37,919 –> 00:05:39,520
اساساً به ما میگوید کجا
152
00:05:39,520 –> 00:05:42,960
در واقع به عقب برگردید، اما همانطور که ممکن
153
00:05:42,960 –> 00:05:44,479
است بتوانید به شما بگویید وقتی
154
00:05:44,479 –> 00:05:46,639
با براکت های تودرتو یا پرانتزهای تودرتو مشکل دارید،
155
00:05:46,639 –> 00:05:49,199
معمولاً یک پشته بسیار
156
00:05:49,199 –> 00:05:51,280
مفید است و در واقع این راهی است که من
157
00:05:51,280 –> 00:05:52,479
این مشکل را حل می
158
00:05:52,479 –> 00:05:54,400
کنم، می توانید آن را به صورت بازگشتی انجام دهید. یا w e واقعاً میتواند
159
00:05:54,400 –> 00:05:57,120
پشتهای را حفظ کند که به
160
00:05:57,120 –> 00:05:59,520
صراحت به ما میگوید وقتی مشکل فرعی را تمام کردید میدانید کجا میتوانیم
161
00:05:59,520 –> 00:06:01,440
162
00:06:01,440 –> 00:06:02,800
پشتیبان
163
00:06:02,800 –> 00:06:04,560
بگیریم، بنابراین اجازه دهید من یک راهحل بسیار سریع
164
00:06:04,560 –> 00:06:06,160
را بررسی
165
00:06:06,160 –> 00:06:08,319
کنم، بنابراین فرض کنید ما داریم برخی از
166
00:06:08,319 –> 00:06:10,240
براکتهای تودرتو مانند این،
167
00:06:10,240 –> 00:06:11,680
بنابراین کاری که میخواهیم با انجام آن شروع کنیم
168
00:06:11,680 –> 00:06:13,680
این است که فقط کاراکتر به
169
00:06:13,680 –> 00:06:16,319
کاراکتر در رشته ورودی و سپس
170
00:06:16,319 –> 00:06:18,479
فقط آن را به پشته اضافه میکنیم تا
171
00:06:18,479 –> 00:06:21,120
ابتدا پنج مورد را ببینیم و تشخیص دهیم که
172
00:06:21,120 –> 00:06:23,360
بله این یک ما تقریباً مطمئن
173
00:06:23,360 –> 00:06:25,440
هستیم که احتمالاً یک براکت افتتاحیه آینده وجود خواهد داشت،
174
00:06:25,440 –> 00:06:27,039
اما
175
00:06:27,039 –> 00:06:28,720
تا زمانی که وجود نداشته باشد کاری انجام نمیدهیم، بنابراین
176
00:06:28,720 –> 00:06:31,039
چهار شخصیت بعدی را
177
00:06:31,039 –> 00:06:32,479
میبینیم که میتوانیم جلو برویم و آن را به آن اضافه کنیم.
178
00:06:32,479 –> 00:06:35,919
هماکنون به یک
179
00:06:35,919 –> 00:06:37,759
براکت باز میرسیم،
180
00:06:37,759 –> 00:06:40,000
این بار دقیقاً همان کار را انجام میدهیم که همچنان آن را
181
00:06:40,000 –> 00:06:41,680
به پشته اضافه میکنیم، اما واضح است که
182
00:06:41,680 –> 00:06:43,759
متوجه میشویم که در یک مشکل
183
00:06:43,759 –> 00:06:46,160
فرعی هستیم و اکنون هر براکت باز
184
00:06:46,160 –> 00:06:48,800
تضمین شده است. به شما می دانید و پس از آن یک
185
00:06:48,800 –> 00:06:51,120
سوتین بسته می شود cet در یک نقطه، بنابراین ما می دانیم
186
00:06:51,120 –> 00:06:53,120
که این مشکل فرعی در نقطه ای به پایان می رسد، در
187
00:06:53,120 –> 00:06:54,880
حال حاضر به کار ادامه می
188
00:06:54,880 –> 00:06:56,080
دهیم، بنابراین نویسه به کاراکتر پیش می رویم
189
00:06:56,080 –> 00:06:58,000
و مطمئن شویم که آن را به
190
00:06:58,000 –> 00:07:00,479
پشته اضافه می کنیم، بنابراین ما حروف کوچک را اضافه می کنیم. با
191
00:07:00,479 –> 00:07:04,960
حروف کوچک b، یک رقم دیگر را اکنون a6 اضافه می کنیم
192
00:07:04,960 –> 00:07:06,960
و سپس به یک براکت باز دیگری
193
00:07:06,960 –> 00:07:08,639
می رسیم و جلو می رویم و آن را به پشته اضافه می کنیم
194
00:07:08,639 –> 00:07:11,520
، بنابراین اکنون وقتی یک
195
00:07:11,520 –> 00:07:13,039
براکت بسته را پیدا کردیم و
196
00:07:13,039 –> 00:07:14,639
این اولین براکت بسته می شود، متوجه می شویم که
197
00:07:14,639 –> 00:07:16,880
روی براکت باز اصلی اعمال نمیشود،
198
00:07:16,880 –> 00:07:19,199
روی
199
00:07:19,199 –> 00:07:21,360
این براکت باز اعمال میشود، زیرا
200
00:07:21,360 –> 00:07:23,599
این جدیدترین براکت باز است و
201
00:07:23,599 –> 00:07:25,840
میتوانیم تشخیص دهیم که از پشته سمت راست
202
00:07:25,840 –> 00:07:27,199
، از
203
00:07:27,199 –> 00:07:29,680
ابتدای پشته شروع میکنیم، ادامه میدهیم. به این ترتیب تا زمانی
204
00:07:29,680 –> 00:07:32,240
که به براکت ابتدایی برسیم و
205
00:07:32,240 –> 00:07:34,080
این اولین موردی است که قرار است
206
00:07:34,080 –> 00:07:35,759
با یک براکت بسته مطابقت داده شود، اما در
207
00:07:35,759 –> 00:07:36,800
حال حاضر کاری که میخواهیم انجام دهیم این است که
208
00:07:36,800 –> 00:07:38,720
کاراکتر به نویسه برویم، خوب، یک
209
00:07:38,720 –> 00:07:41,759
حرف کوچک c میبینیم، میگوییم کوچک d ما می
210
00:07:41,759 –> 00:07:44,800
توانید آن را به پشته a اضافه کنید خوب است و اکنون
211
00:07:44,800 –> 00:07:47,039
ما به اولین براکت بسته خود می رسیم و
212
00:07:47,039 –> 00:07:49,039
بنابراین این تنها شرط است،
213
00:07:49,039 –> 00:07:51,120
براکت بسته شدن واقعاً تنها نقطه ای است
214
00:07:51,120 –> 00:07:52,400
که می خواهیم کار
215
00:07:52,400 –> 00:07:54,160
متفاوتی انجام دهیم،
216
00:07:54,160 –> 00:07:56,080
البته این براکت بسته شدن را نخواهیم گرفت و آن را درست به پشته اضافه کنید
217
00:07:56,080 –> 00:07:58,080
زیرا در راه حل
218
00:07:58,080 –> 00:08:00,080
ما واقعاً به براکت ها اهمیت نمی دهیم تنها چیزی
219
00:08:00,080 –> 00:08:03,199
که اکنون می دانیم این است که
220
00:08:03,199 –> 00:08:04,319
این
221
00:08:04,319 –> 00:08:07,120
براکت را به درستی تکمیل کرده ایم، بنابراین هر چیزی
222
00:08:07,120 –> 00:08:09,199
که در داخل این براکت بود چگونه
223
00:08:09,199 –> 00:08:10,960
همه چیزهایی را که در داخل آن بود به دست آوریم. ما
224
00:08:10,960 –> 00:08:12,960
می دانیم که این یک سی دی است که چگونه می توانیم آنقدر خوب به دست
225
00:08:12,96