در این مطلب، ویدئو ویرایش فاصله – برنامه نویسی پویا – Leetcode 72 – Python با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:21:00
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,000 –> 00:00:01,760
سلام به همه خوش آمدید و بیایید
2
00:00:01,760 –> 00:00:03,760
امروز یک کد دقیق تر بنویسیم، بنابراین امروز
3
00:00:03,760 –> 00:00:04,560
بیایید فاصله ویرایش را حل کنیم،
4
00:00:04,560 –> 00:00:06,960
بنابراین این یک
5
00:00:06,960 –> 00:00:08,480
مشکل برنامه نویسی پویا است و
6
00:00:08,480 –> 00:00:11,040
بسیار شبیه به طولانی ترین مشکل
7
00:00:11,040 –> 00:00:13,040
متداول است که مشکلی است
8
00:00:13,040 –> 00:00:14,880
که من در این کانال حل کرده ام، بنابراین
9
00:00:14,880 –> 00:00:17,119
این مشکل اساساً
10
00:00:17,119 –> 00:00:18,400
گسترش آن مشکل است،
11
00:00:18,400 –> 00:00:21,039
بنابراین به ما دو رشته کلمه یک و
12
00:00:21,039 –> 00:00:21,840
کلمه دو داده می شود
13
00:00:21,840 –> 00:00:24,480
و هدف ما این است که حداقل
14
00:00:24,480 –> 00:00:25,359
تعداد
15
00:00:25,359 –> 00:00:28,640
عملیات لازم برای گرفتن کلمه یک
16
00:00:28,640 –> 00:00:32,320
و تبدیل آن به کلمه دو را برگردانیم و ما فقط
17
00:00:32,320 –> 00:00:32,960
18
00:00:32,960 –> 00:00:35,840
سه عملیات در دسترس داریم.
19
00:00:35,840 –> 00:00:37,280
درج یک کاراکتر
20
00:00:37,280 –> 00:00:39,120
در کلمه یک درست به خاطر داشته باشید زیرا
21
00:00:39,120 –> 00:00:40,719
ما سعی می کنیم کلمه یک را بگیریم و
22
00:00:40,719 –> 00:00:41,520
آن را
23
00:00:41,520 –> 00:00:44,399
به کلمه دو تبدیل کنیم نمی توانیم کلمه دو را تغییر
24
00:00:44,399 –> 00:00:46,079
دهیم می توانیم یک کاراکتر را
25
00:00:46,079 –> 00:00:47,840
از کلمه یک حذف کنیم زیرا نمی توانیم
26
00:00:47,840 –> 00:00:50,800
کلمه دو را تغییر دهیم و می توانیم جایگزین کنیم یک کاراکتر
27
00:00:50,800 –> 00:00:53,280
در کلمه یک و بنابراین جایگزین کردن یک
28
00:00:53,280 –> 00:00:54,559
کاراکتر اساساً تغییر
29
00:00:54,559 –> 00:00:57,360
یک کاراکتر به کاراکتر دیگر است، بنابراین در این
30
00:00:57,360 –> 00:00:57,840
31
00:00:57,840 –> 00:00:59,600
مورد سه عملیات لازم است
32
00:00:59,600 –> 00:01:01,760
تا اسب را بگیرید و آن را به
33
00:01:01,760 –> 00:01:04,000
این رشته از c تبدیل کنید. ما میخواهیم از
34
00:01:04,000 –> 00:01:04,959
شر
35
00:01:04,959 –> 00:01:06,960
h راست خلاص شویم، اما این کار را با
36
00:01:06,960 –> 00:01:08,640
جایگزین کردن h با
37
00:01:08,640 –> 00:01:11,439
r انجام میدهیم، بنابراین این یک r میشود و سپس
38
00:01:11,439 –> 00:01:12,000
39
00:01:12,000 –> 00:01:15,119
دو راست R را داریم، بنابراین از شر این r خلاص
40
00:01:15,119 –> 00:01:15,759
میشویم.
41
00:01:15,759 –> 00:01:18,560
میتوانیم از شر آن خلاص شویم و در نهایت میبینیم که
42
00:01:18,560 –> 00:01:18,880
43
00:01:18,880 –> 00:01:21,920
ما یک e اضافی داریم، بنابراین
44
00:01:21,920 –> 00:01:22,320
میخواهیم از
45
00:01:22,320 –> 00:01:24,960
شر e نیز خلاص شویم، بنابراین این کار را در
46
00:01:24,960 –> 00:01:26,159
سه عملیات انجام
47
00:01:26,159 –> 00:01:28,640
دادیم، بنابراین میتوانیم سه مورد را برگردانیم، بنابراین اول از همه
48
00:01:28,640 –> 00:01:31,119
بیایید چند مورد ساده را تجزیه و تحلیل کنیم. موارد
49
00:01:31,119 –> 00:01:33,520
چه می شود اگر ما حالتی را داشتیم که کلمه یک
50
00:01:33,520 –> 00:01:35,119
و کلمه دو هر دو
51
00:01:35,119 –> 00:01:37,280
فقط رشته های خالی بودند، چند
52
00:01:37,280 –> 00:01:39,040
عملیات طول می کشد، سپس برای گرفتن کلمه یک و
53
00:01:39,040 –> 00:01:40,320
تبدیل آن به کلمه دو،
54
00:01:40,320 –> 00:01:42,079
واضح است که به طور واضح صفر درست است، لازم نیست
55
00:01:42,079 –> 00:01:44,240
کاری انجام دهیم که قبلاً انجام شده اند. به همین
56
00:01:44,240 –> 00:01:47,119
ترتیب، اگر کلمه یک بود، بیایید بگوییم abc
57
00:01:47,119 –> 00:01:47,920
و کلمه
58
00:01:47,920 –> 00:01:51,040
دو نیز یک b c است، ما همچنین
59
00:01:51,040 –> 00:01:52,479
مجبور نیستیم کاری را درست انجام دهیم
60
00:01:52,479 –> 00:01:54,399
، به اولین کاراکتر نگاه می کنیم و ببینید اوه
61
00:01:54,399 –> 00:01:55,520
آنها درست هستند،
62
00:01:55,520 –> 00:01:57,360
زیرا البته آنها یکسان هستند. دیگر
63
00:01:57,360 –> 00:01:58,880
لازم نیست آنها را درست در نظر بگیریم،
64
00:01:58,880 –> 00:01:59,280
65
00:01:59,280 –> 00:02:01,200
سپس تنها کاری که باید انجام دهیم این است که
66
00:02:01,200 –> 00:02:03,119
باقیمانده هر رشته را به سمت راست مقایسه کنیم، اما n
67
00:02:03,119 –> 00:02:04,640
دوباره می بینیم هی
68
00:02:04,640 –> 00:02:07,840
b همان خوب است c نیز همان
69
00:02:07,840 –> 00:02:10,560
خوب است و کاملاً زمان بندی شده به نظر می رسد،
70
00:02:10,560 –> 00:02:12,239
هیچ کاراکتری در کلمه یک باقی نمی ماند و
71
00:02:12,239 –> 00:02:13,920
هیچ کاراکتری در کلمه دو باقی نمی ماند،
72
00:02:13,920 –> 00:02:16,560
بنابراین عملیات صفر مورد نیاز بود
73
00:02:16,560 –> 00:02:17,440
74
00:02:17,440 –> 00:02:20,560
درست اگر کلمه یک abc
75
00:02:20,560 –> 00:02:23,520
و کلمه دو بود. خالی بود، پس چه
76
00:02:23,520 –> 00:02:25,520
کار میکردیم، حتی ممکن است این کلمه را بگیریم
77
00:02:25,520 –> 00:02:27,040
و سپس آن را به خالی تبدیل کنیم،
78
00:02:27,040 –> 00:02:29,760
البته در این مشکل
79
00:02:29,760 –> 00:02:30,239
80
00:02:30,239 –> 00:02:32,480
همیشه میتوان کلمه
81
00:02:32,480 –> 00:02:34,160
یک را گرفت و آن را به کلمه دو تبدیل کرد
82
00:02:34,160 –> 00:02:36,160
زیرا میتوانیم آن را وارد کنیم. یک کاراکتر میتوانیم یک کاراکتر را
83
00:02:36,160 –> 00:02:37,440
حذف
84
00:02:37,440 –> 00:02:39,280
کنیم یا میتوانیم یک کاراکتر را جایگزین کنیم، بنابراین
85
00:02:39,280 –> 00:02:40,879
همیشه امکانپذیر است،
86
00:02:40,879 –> 00:02:43,680
زیرا در بدترین حالت، این همان
87
00:02:43,680 –> 00:02:44,480
کاری است که میتوانیم انجام
88
00:02:44,480 –> 00:02:46,720
دهیم، میتوانیم تک تک کاراکترها را در
89
00:02:46,720 –> 00:02:48,319
کلمه یک برداریم و فقط آن را حذف کنیم،
90
00:02:48,319 –> 00:02:50,080
حذف آن حذف شود زیرا هیچکدام از
91
00:02:50,080 –> 00:02:51,519
اینها در کلمه دو نشان داده نمی شوند،
92
00:02:51,519 –> 00:02:53,440
فقط اگر یک کاراکتر وجود داشت، همه آنها را حذف کنید،
93
00:02:53,440 –> 00:02:55,120
شاید یک z در
94
00:02:55,120 –> 00:02:55,519
اینجا وجود
95
00:02:55,519 –> 00:02:57,599
داشته باشد، پس از اینکه آنها را حذف کردیم، فقط می توانیم هر کاراکتری را کپی
96
00:02:57,599 –> 00:02:59,040
کنیم
97
00:02:59,040 –> 00:03:00,800
و سپس آن را در اینجا کپی کنیم. dd
98
00:03:00,800 –> 00:03:02,560
که z، اما نه ما نیازی به این کار نداریم،
99
00:03:02,560 –> 00:03:05,519
بنابراین سوال من از شما این است که اگر کلمه دو
100
00:03:05,519 –> 00:03:06,080
خالی است
101
00:03:06,080 –> 00:03:08,800
و کلمه یک خالی نیست، پس
102
00:03:08,800 –> 00:03:09,920
این چه چیزی است
103
00:03:09,920 –> 00:03:11,760
که چند عملیات طول می کشد
104
00:03:11,760 –> 00:03:14,319
همیشه طول می کشد.
105
00:03:14,319 –> 00:03:16,159
طول کلمه یک هر چه باشد،
106
00:03:16,159 –> 00:03:17,440
زیرا ما باید
107
00:03:17,440 –> 00:03:19,680
تک تک کاراکترها را درست حذف کنیم، به طوری که
108
00:03:19,680 –> 00:03:21,519
یک مورد اصلی کلمه دو خالی است
109
00:03:21,519 –> 00:03:23,519
، در مورد حروف مقابل، اگر
110
00:03:23,519 –> 00:03:25,200
کلمه دو abc بود
111
00:03:25,200 –> 00:03:27,920
و کلمه یک خالی بود، آیا این امکان
112
00:03:27,920 –> 00:03:29,440
وجود دارد؟ ممکن است کلمه یک را برداریم و
113
00:03:29,440 –> 00:03:30,799
آن را به کلمه دو تبدیل کنیم
114
00:03:30,799 –> 00:03:32,159
البته درست است زیرا ما
115
00:03:32,159 –> 00:03:34,319
مجاز به وارد کردن کاراکترها در اینجا هستیم بنابراین
116
00:03:34,319 –> 00:03:36,000
اساساً می توانیم کاراکتر
117
00:03:36,000 –> 00:03:37,200
به کاراکتر a
118
00:03:37,200 –> 00:03:40,159
را بخوانیم که در اینجا b اضافه کنیم که اینجا c آن را
119
00:03:40,159 –> 00:03:40,560
اینجا
120
00:03:40,560 –> 00:03:42,319
نیز اضافه کنیم. بنابراین ما فقط می توانیم هر کاراکتری را کپی کنیم،
121
00:03:42,319 –> 00:03:44,480
بنابراین سؤال من از شما
122
00:03:44,480 –> 00:03:46,959
در این مورد این است که در این حالت، در حالت مخالف است که
123
00:03:46,959 –> 00:03:47,840
کلمه
124
00:03:47,840 –> 00:03:50,640
دو خالی نیست اما کلمه یک خالی است
125
00:03:50,640 –> 00:03:52,080
126
00:03:52,080 –> 00:03:52,560
127
00:03:52,560 –> 00:03:54,959
. درست است بنابراین در
128
00:03:54,959 –> 00:03:56,720
این مورد آن را می خواهم
129
00:03:56,720 –> 00:03:59,120
طول کلمه دو را در نظر بگیرید که چند عملیات
130
00:03:59,120 –> 00:04:00,640
درست انجام می شود، بنابراین اساساً
131
00:04:00,640 –> 00:04:02,000
چیزی که من به آن می پردازم این است که اگر
132
00:04:02,000 –> 00:04:04,480
کلمه یک خالی و کلمه
133
00:04:04,480 –> 00:04:05,360
دو خالی نباشد،
134
00:04:05,360 –> 00:04:07,120
ما طول آن را
135
00:04:07,120 –> 00:04:09,840
به عنوان حداقل عدد برمی گردانیم.
136
00:04:09,840 –> 00:04:12,400
اگر برعکس درست بود، ممکن است
137
00:04:12,400 –> 00:04:14,560
این خالی باشد، اما خالی نیست، پس
138
00:04:14,560 –> 00:04:17,040
139
00:04:17,040 –> 00:04:18,560
اگر یکی از آنها خالی باشد
140
00:04:18,560 –> 00:04:20,639
، طول رشته غیر خالی را برمی
141
00:04:20,639 –> 00:04:22,160
گردانیم. این حداقل
142
00:04:22,160 –> 00:04:23,360
تعداد عملیات خواهد بود،
143
00:04:23,360 –> 00:04:24,880
این مهم است زیرا این
144
00:04:24,880 –> 00:04:27,520
مورد پایه ما است، بنابراین اکنون بیایید سعی کنیم به زور بی رحمانه
145
00:04:27,520 –> 00:04:28,320
این
146
00:04:28,320 –> 00:04:29,759
کار را انجام دهیم.
147
00:04:29,759 –> 00:04:31,120
148
00:04:31,120 –> 00:04:32,320
149
00:04:32,320 –> 00:04:34,160
اشاره گر به یک کاراکتر در کلمه یک و
150
00:04:34,160 –> 00:04:35,840
اشاره گر دوم به یک کاراکتر
151
00:04:35,840 –> 00:04:37,520
در کلمه دو اشاره می کند، ما کاراکتر به کاراکتر را با هم مقایسه می کنیم،
152
00:04:37,520 –> 00:04:38,800
153
00:04:38,800 –> 00:04:41,680
بنابراین یک مورد این است که اگر
154
00:04:41,680 –> 00:04:43,120
دقیقاً برابر باشند،
155
00:04:43,120 –> 00:04:45,440
پس مشکل فرعی چیست،
156
00:04:45,440 –> 00:04:46,880
درست است زیرا ما مجبور نیستیم
157
00:04:46,880 –> 00:04:48,080
این کاراکترها را در نظر بگیریم cters دیگر
158
00:04:48,080 –> 00:04:49,840
اکنون ما با مشکل فرعی
159
00:04:49,840 –> 00:04:51,600
160
00:04:51,600 –> 00:04:53,759
باقیمانده آن رشته ها سر و کار داریم، بنابراین اگر من
161
00:04:53,759 –> 00:04:55,600
اشاره گر را در کلمه یک
162
00:04:55,600 –> 00:04:57,600
i صدا می زنم و اگر این کاراکترها مساوی هستند اشاره گر را در کلمه به j فرا می خوانم، به
163
00:04:57,600 –> 00:05:00,639
این معنی است که
164
00:05:00,639 –> 00:05:03,680
اساساً میتوانیم بگوییم i به علاوه یک
165
00:05:03,680 –> 00:05:04,720
مسئله جدید است و
166
00:05:04,720 –> 00:05:07,520
j به علاوه یک مشکل جدید در
167
00:05:07,520 –> 00:05:08,479
کلمه دو به سمت راست است، بنابراین
168
00:05:08,479 –> 00:05:09,919
ما فقط نشانگرهای خود را به این شکل تغییر
169
00:05:09,919 –> 00:05:12,320
میدهیم تا خلاصه
170
00:05:12,320 –> 00:05:14,479
کنیم که آیا این کاراکترها دقیقاً در i و j برابر هستند یا خیر.
171
00:05:14,479 –> 00:05:15,360
172
00:05:15,360 –> 00:05:16,800
اساساً به چیزی که من می گویم
173
00:05:16,800 –> 00:05:18,080
کاراکترها برابر هستند اشاره کنید، سپس ما فقط
174
00:05:18,080 –> 00:05:19,759
i را 1
175
00:05:19,759 –> 00:05:21,919
و j را به 1 افزایش
176
00:05:21,919 –> 00:05:23,840
177
00:05:23,840 –> 00:05:25,360
می دهیم.
178
00:05:25,360 –> 00:05:27,280
قبلاً برابر بود، ما اصلاً مجبور نبودیم
179
00:05:27,280 –> 00:05:27,680
180
00:05:27,680 –> 00:05:30,160
کلمه یک را به کاراکتر بعدی
181
00:05:30,160 –> 00:05:31,120
تغییر دهیم، بنابراین نشانگر i ما
182
00:05:31,120 –> 00:05:32,639
در اینجا خواهد بود نشانگر j ما
183
00:05:32,639 –> 00:05:33,840
اینجا خواهد بود زیرا
184
00:05:33,840 –> 00:05:35,919
هر دوی آنها را یک افزایش دادیم، بنابراین حالا
185
00:05:35,919 –> 00:05:37,520
بیایید کاراکترهای c را با هم مقایسه کنیم.
186
00:05:37,520 –> 00:05:41,039
و b در حال حاضر برابر نیستند، بنابراین در حال حاضر شرایط
187
00:05:41,039 –> 00:05:42,960
دیگری ما به شرطی که قرار است
188
00:05:42,960 –> 00:05:44,560
اجرا شود و ما نمی دانیم که
189
00:05:44,560 –> 00:05:46,800
می دانیم سه گزینه داریم که می توانیم
190
00:05:46,800 –> 00:05:47,840
یک کاراکتر وارد کنیم یک کاراکتر را
191
00:05:47,840 –> 00:05:49,919
حذف کنیم یا یک
192
00:05:49,919 –> 00:05:51,759
کاراکتر را از کلمه یک جایگزین
193
00:05:51,759 –> 00:05:54,240
کنیم، اما نمی دانیم کدام یک را درست انجام دهیم،
194
00:05:54,240 –> 00:05:55,600
بنابراین بیایید
195
00:05:55,600 –> 00:05:58,800
هر سه را امتحان کنیم چه اتفاقی میافتد اگر
196
00:05:58,800 –> 00:06:01,039
یک کاراکتر را وارد کنیم، چه کاراکتری را میخواهیم
197
00:06:01,039 –> 00:06:02,560
در اینجا وارد کنیم،
198
00:06:02,560 –> 00:06:04,080
بدیهی است که میخواهیم
199
00:06:04,080 –> 00:06:06,240
کاراکتر را از کلمه دو وارد کنیم.
200
00:06:06,240 –> 00:06:08,639
201
00:06:08,639 –> 00:06:10,880
202
00:06:10,880 –> 00:06:13,039
عملیات، اما بیایید
203
00:06:13,039 –> 00:06:14,800
آن را امتحان کنیم و ببینیم چه اتفاقی می افتد،
204
00:06:14,800 –> 00:06:17,919
بنابراین اگر
205
00:06:17,919 –> 00:06:21,039
یک c را درست در اینجا وارد کنیم، چه کار می کنیم، یک
206
00:06:21,039 –> 00:06:23,199
کاراکتر را حذف نمی کنیم، تنها کاری که انجام می دهیم این است که یک
207
00:06:23,199 –> 00:06:23,520
c
208
00:06:23,520 –> 00:06:27,280
را در اینجا وارد کنیم، در این صورت نشانگر i ما
209
00:06:27,280 –> 00:06:30,080
همچنان به به سمت این b به سمت راست اشاره کنید،
210
00:06:30,080 –> 00:06:30,479
211
00:06:30,479 –> 00:06:33,360
اما از آنجایی که ما یک c را در اینجا وارد کرده ایم،
212
00:06:33,360 –> 00:06:34,000
خواندن آن سخت است،
213
00:06:34,000 –> 00:06:36,319
اما فرض کنید من یک c را در
214
00:06:36,319 –> 00:06:37,280
بین اینجا وارد کرده ام،
215
00:06:37,280 –> 00:06:39,759
این بدان معناست که ما از c از
216
00:06:39,759 –> 00:06:41,039
کلمه دو به درستی مراقبت کرده ایم، بنابراین
217
00:06:41,039 –> 00:06:43,039
اساساً نیازی به یافتن تطابق نداریم.
218
00:06:43,039 –> 00:06:45,360
ج برای آن دیگر ما انجام می دهیم برای
219
00:06:45,360 –> 00:06:46,479
پیدا کردن یک b منطبق در
220
00:06:46,479 –> 00:06:48,800
جایی در اینجا درست است، بنابراین
221
00:06:48,800 –> 00:06:49,759
ما نشانگر i خود را
222
00:06:49,759 –> 00:06:51,680
در جایی که هست رها می کنیم، اما
223
00:06:51,680 –> 00:06:54,160
نشانگر j خود را می گیریم و سپس آن را به
224
00:06:54,160 –> 00:06:55,120
موقعیت بعدی
225
00:06:55,120 –> 00:06:57,520
در کلمه دو منتقل می کنیم، این همان کاری است که اگر درج کنیم این کار را انجام می
226
00:06:57,520 –> 00:06:59,039
دهیم. یک
227
00:06:59,039 –> 00:07:01,599
کاراکتر، همانطور که میبینید وقتی یک
228
00:07:01,599 –> 00:07:02,240
کاراکتر را وارد
229
00:07:02,240 –> 00:07:04,560
میکنیم، یک عملیات را درست
230
00:07:04,560 –> 00:07:06,080
انجام میدهیم، بنابراین باید یک کاراکتر را به
231
00:07:06,080 –> 00:07:07,520
تعداد عملیاتی که انجام دادهایم اضافه کنیم،
232
00:07:07,520 –> 00:07:10,240
اما وقتی نشانگرهای خود را تغییر میدهیم
233
00:07:10,240 –> 00:07:10,800
، نشانگر i
234
00:07:10,800 –> 00:07:13,840
دقیقاً یکسان میماند. اما j
235
00:07:13,840 –> 00:07:16,960
با یک افزایش می یابد، بنابراین یک
236
00:07:16,960 –> 00:07:18,319
237
00:07:18,319 –> 00:07:20,319
احتمال دیگر این است که ما یک کاراکتر را حذف می کنیم،
238
00:07:20,319 –> 00:07:22,240
بنابراین ما مجاز به حذف
239
00:07:22,240 –> 00:07:23,280
کاراکترها
240
00:07:23,280 –> 00:07:25,360
از کلمه یک خود هستیم، بنابراین
241
00:07:25,360 –> 00:07:27,120
اگر من فقط این کاراکتر را حذف کنم، چیزی
242
00:07:27,120 –> 00:07:28,240
که می گوییم
243
00:07:28,240 –> 00:07:31,680
خوب است، می توانم چه اتفاقی می افتد. یک c منطبق را در این
244
00:07:31,680 –> 00:07:32,960
موقعیت درست پیدا کنید
245
00:07:32,960 –> 00:07:34,639
و ما و ما یک b
246
00:07:34,639 –> 00:07:36,639
متناظر با آن موقعیت نداریم، بنابراین من
247
00:07:36,639 –> 00:07:38,560
فقط این شخص را نادیده میگیرم
248
00:07:38,560 –> 00:07:40,880
و امیدوارم بقیه
249
00:07:40,880 –> 00:07:42,639
رشتهها درست مطابقت داشته باشند، بنابراین آنچه
250
00:07:42,639 –> 00:07:44,080
میگویم این است من می خواهم
251
00:07:44,080 –> 00:07:46,160
اشاره گر چشم ما را بگیرم و بله من می خواهم
252
00:07:46,160 –> 00:07:48,080
آن را به موقعیت بعدی تغییر دهم زیرا فقط
253
00:07:48,080 –> 00:07:49,680
می خواهم وانمود کنم که این کاراکتر
254
00:07:49,680 –> 00:07:52,400
هرگز وجود نداشته است، اما
255
00:07:52,400 –> 00:07:54,800
برای تکمیل آن یک عملیات لازم است، اما از آنجایی که ما
256
00:07:54,800 –> 00:07:55,360
257
00:07:55,360 –> 00:07:58,000
یک c منطبق و هنوز درست پیدا نکردیم، باید
258
00:07:58,000 –> 00:07:59,680
نشانگر j خود را اینجا بگذاریم. درست است، ما باید
259
00:07:59,680 –> 00:08:01,840
به جستجو ادامه دهیم تا زمانی که C منطبق را پیدا کنیم،
260
00:08:01,840 –> 00:08:02,720
261
00:08:02,720 –> 00:08:05,360
در نهایت می خواهیم کلمه یک با کلمه دو مطابقت داشته باشد،
262
00:08:05,360 –> 00:08:06,319
263
00:08:06,319 –> 00:08:08,879
بنابراین در این مورد برای عملیات حذف،
264
00:08:08,879 –> 00:08:10,720
چیزی که می گوییم این است که i قرار است
265
00:08:10,720 –> 00:08:13,280
جابجا شود، اما j دقیقاً یکسان می ماند.
266
00:08:13,280 –> 00:08:17,199
بنابراین من به اضافه 1 اما j همان
267
00:08:17,199 –> 00:08:20,160
طور که می بینید باقی می ماند این است که می دانید یک نوع
268
00:08:20,160 –> 00:08:21,599
الگو است که ما شروع به دیدن یک
269
00:08:21,599 –> 00:08:22,639
الگوی درست می کنیم
270
00:08:22,639 –> 00:08:24,800
و آخرین کاری که می توانیم انجام دهیم این است که
271
00:08:24,800 –> 00:08:25,680
272
00:08:25,680 –> 00:08:29,120
یک کاراکتر از کلمه یک که در word نشان داده می شود را جایگزین کنیم.
273
00:08:29,120 –> 00:08:30,720
بدیهی است که اگر
274
00:08:30,720 –> 00:08:32,399
یک کاراکتر را از کلمه
275
00:08:32,399 –> 00:08:34,240
یک به درستی جایگزین کنیم، باید کاراکتری را بخواهیم
276
00:08:34,240 –> 00:08:35,440
که در کلمه دو مطابقت داشته باشد،
277
00:08:35,440 –> 00:08:37,279
بنابراین کاری که میخواهیم انجام دهیم این
278
00:08:37,279 –> 00:08:38,479
است که این b را برداریم
279
00:08:38,479 –> 00:08:42,080
و
280
00:08:42,080 –> 00:08:44,800
اگر به وضوح این کار را انجام دادیم، آن را با یک کاراکتر c جایگزین کنیم. این دو
281
00:08:44,800 –> 00:08:46,160
شخصیت درست مطابقت دارند که ما آن را
282
00:08:46,160 –> 00:08:48,320
ساختیم منطبق m، ما این
283
00:08:48,320 –> 00:08:49,600
کاراکترها را مجبور کردیم با هم مطابقت داشته
284
00:08:49,600 –> 00:08:52,160
باشند، بنابراین در این صورت می دانیم که c
285
00:08:52,160 –> 00:08:53,120
در اینجا یک c منطبق
286
00:08:53,120 –> 00:08:55,360
دارد، بنابراین می توانیم این نشانگر i
287
00:08:55,360 –> 00:08:57,440
را برداریم و آن را تغییر دهیم و می توانیم نشانگر j خود را برداریم
288
00:08:57,440 –> 00:08:59,360
و آن را به موقعیت بعدی
289
00:08:59,360 –> 00:09:00,800
درست تغییر دهیم.
290
00:09:00,800 –> 00:09:03,680
جایگزین در واقع
291
00:09:03,680 –> 00:09:04,959
دقیقاً همان کاری را انجام می دهد که
292
00:09:04,959 –> 00:09:07,120
اگر کاراکترها برابر هستند و این
293
00:09:07,120 –> 00:09:08,959
منطقی است زیرا کاری که ما انجام می
294
00:09:08,959 –> 00:09:09,360
دهیم این است
295
00:09:09,360 –> 00:09:11,519
که آنها را مجبور می کنیم با عملیات جایگزینی برابر باشند
296
00:09:11,519 –> 00:09:12,880
297
00:09:12,880 –> 00:09:15,519
تفاوت بین جایگزینی و
298
00:09:15,519 –> 00:09:17,519
و اگر قبلاً بودند در اصل
299
00:09:17,519 –> 00:09:18,000
برابر
300
00:09:18,000 –> 00:09:20,959
این است که جایگزینی یک عملیات واحد را
301
00:09:20,959 –> 00:09:23,519
انجام می دهد در صورتی که قبلاً
302
00:09:23,519 –> 00:09:25,519
برابر بود تعداد عملیاتی که انجام می دهد صفر است،
303
00:09:25,519 –> 00:09:26,560
304
00:09:26,560 –> 00:09:28,880
بنابراین هزینه دارد حتی اگر
305
00:09:28,880 –> 00:09:30,880
جایگزینی بسیار قدرتمند است
306
00:09:30,880 –> 00:09:32,480
همانطور که گفتم با جایگزینی کاری که می خواهیم
307
00:09:32,480 –> 00:09:34,000
انجام دهیم. افزایش i
308
00:09:34,000 –> 00:09:37,360
و افزایش j است، بنابراین اجازه دهید
309
00:09:37,360 –> 00:09:38,959
عملیات جایگزینی را انجام دهیم زیرا در
310
00:09:38,959 –> 00:09:40,160
واقع
311
00:09:40,160 –> 00:09:42,240
این حداقل راه حل است، بنابراین اکنون
312
00:09:42,240 –> 00:09:43,440
نشانگرهای خود را به موقعیت بعدی
313
00:09:43,440 –> 00:09:44,320
که می بینیم
314
00:09:44,320 –> 00:09:46,880
d و d با یکدیگر مطابقت دارند تغییر می دهیم. o این دستوری
315
00:09:46,880 –> 00:09:48,240
است که قرار است اجرا شود
316
00:09:48,240 –> 00:09:49,600
و ما می دانیم که 0
317
00:09:49,600 –> 00:09:50,800
عملیات را درست انجام می دهد، بنابراین
318
00:09:50,800 –> 00:09:53,200
هر دو نشانگر را 1 افزایش
319
00:09:53,200 –> 00:09:55,120
320
00:09:55,120 –> 00:09:57,360
می دهیم.
321
00:09:57,360 –> 00:09:58,000
322
00:09:58,000 –> 00:10:00,160
رشته های خالی حالت پایه را به خاطر می آورند اگر
323
00:10:00,160 –> 00:10:01,680
هر دو رشته خالی هستند،
324
00:10:01,680 –> 00:10:04,000
می توانیم 0 را برگردانیم، زیرا صفر عملیات طول می کشد
325
00:10:04,000 –> 00:10:05,600
تا آنها
326
00:10:05,600 –> 00:10:07,440
برابر باشند، آنها از قبل مساوی هستند، بنابراین
327
00:10:07,440 –> 00:10:09,440
ما تمام کردیم،
328
00:10:09,440 –> 00:10:11,839
صفر را برمی گردانیم که چند عملیات انجام
329
00:10:11,839 –> 00:10:12,480
شده است اگر ما
330
00:10:12,480 –> 00:10:14,000
شما حساب می کردید که ما مجبور بودیم
331
00:10:14,000 –> 00:10:15,920
یک عملیات جایگزینی را
332
00:10:15,920 –> 00:10:18,480
اجرا کنیم که یک عملیات طول کشید، بنابراین
333
00:10:18,480 –> 00:10:19,600
نتیجه
334
00:10:19,600 –> 00:10:21,920
یک است، بنابراین ما متوجه می شویم که مشکلات فرعی
335
00:10:21,920 –> 00:10:22,640
336
00:10:22,640 –> 00:10:24,959
حل می شوند قبل از اینکه بخواهیم
337
00:10:24,959 –> 00:10:25,920
338
00:10:25,920 –> 00:10:28,079
مشکل اصلی مقایسه کل لیست ها را حل
339
00:10:28,079 –> 00:10:29