Нэг string-ийг нөгөө string болгоход хэрэгтэй хамгийн цөөн үйлдлийг (устгах, нэмэх, солих) хүснэгтээр олно.

Advanced & LegendХугацаа: O(n · m)Санах ой: O(n · m)

Эхлээд жижиг бодлого

"CAT"-ийг "CUT" болгоё. Нэг үйлдлээр нэг үсэг устгах, нэмэх эсвэл солих боломжтой.

A-г U-гаар солиход л болно, хариу 1. Харин "AB"-г "BA" болгоход 2 үйлдэл хэрэгтэй: хоёр үсгийг хоёуланг нь солино, эсвэл A-г устгаад ард нь нэмнэ.

Энгийн аргаас санаа руу

Энгийн арга бол бүх боломжит үйлдлийн дарааллыг туршиж үзэх. Алхам бүрт гурван сонголт тул хэдхэн алхамд л хэтэрхий олон болно.

Гол санаа: хоёр string-ийн сүүлийн үсгийг харна. Ижил бол юу ч хийх хэрэггүй: dp[i][j] = dp[i - 1][j - 1]. Өөр бол сүүлийн үйлдэл гурван янз: s-ийн сүүлийн үсгийг устгах dp[i - 1][j], t-ийн сүүлийн үсгийг нэмэх dp[i][j - 1], сүүлийн үсгийг солих dp[i - 1][j - 1]. Хамгийн багыг нь аваад 1 нэмнэ.

Нэр томьёо ба тэмдэглэгээ

dp[i][j]
State: s-ийн эхний i үсгийг t-ийн эхний j үсэг болгох хамгийн цөөн үйлдэл.
base case
dp[i][0] = i: бүх үсгийг устгана. dp[0][j] = j: бүх үсгийг нэмнэ.
устгах, нэмэх, солих
Дээрх, зүүн, зүүн дээд нүд. Аль нүдийг сонгосноор ямар үйлдэл хийснийг мэднэ.
Levenshtein distance
Edit Distance-ийн өөр нэр.
s \ tSNOWY
S
U
N
N
Y

s = SUNNY string-ийг t = SNOWY болгоё. Нэг үйлдлээр нэг үсэг устгах, нэмэх эсвэл солих боломжтой. Хамгийн цөөндөө хэдэн үйлдэл хэрэгтэй вэ? State: dp[i][j] нь s-ийн эхний i үсгийг t-ийн эхний j үсэг болгох хамгийн цөөн үйлдэл.

Алхам 1 / 29
Хурд
  • Бөглөж буй нүд
  • Transition-д уншиж буй нүд
  • Бөглөсөн
  • Хариу ба үйлдлийн зам
Слайд 1 / 6

Нэг string-ийг нөгөө болгох

SUNNY-г SNOWY болгоё. Нэг үйлдлээр нэг үсэг устгах, нэмэх эсвэл солих боломжтой. Хамгийн цөөндөө хэдэн үйлдэл хэрэгтэй вэ?

edit-distance.cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, dp[1005][1005];
string s, t;
int main() {
cin >> s >> t;
n = s.size(), m = t.size();
for (int i = 0; i <= n; i++) dp[i][0] = i;
for (int j = 0; j <= m; j++) dp[0][j] = j;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
}
}
}
cout << dp[n][m] << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Үсгийн алдаа засагч, хайлтын "Та үүнийг хайсан уу?" санал ийм зайгаар ойролцоо үгийг олдог. Хоёр string-ийг харьцуулдаг сонгодог DP бодлого.

Яаж ажилладаг вэ?

1. State: dp[i][j] нь s-ийн эхний i үсгийг t-ийн эхний j үсэг болгох хамгийн цөөн үйлдэл. 2. Base case: dp[i][0] = i (бүгдийг устгана), dp[0][j] = j (бүгдийг нэмнэ). 3. s[i − 1] = t[j − 1] бол: dp[i][j] = dp[i − 1][j − 1]. 4. Өөр бол: dp[i][j] = 1 + min(dp[i − 1][j], dp[i][j − 1], dp[i − 1][j − 1]). Эдгээр нь дарааллаараа устгах, нэмэх, солих. 5. Хариу нь dp[n][m]. Оролт: хоёр мөрөнд s ба t string.

Яагаад зөв, хэр хурдан бэ?

Хамгийн сайн үйлдлийн дарааллыг s-ийн сүүлийн үсгээр нь ангилъя: тэр үсэг устсан, тэр үсэг t-ийн сүүлийн үсэг болсон (ижил эсвэл солигдсон), эсвэл t-ийн сүүлийн үсэг шинээр нэмэгдсэн. Өөр боломж байхгүй, гурвуулаа transition-д бий.

Хугацаа ба санах ой O(n · m). Хоёр 1000 үсэгтэй string-д сая нүд.

Түгээмэл алдаа

  • Base case-ийг мартах. Хашаа 0 биш, dp[i][0] = i, dp[0][j] = j байх ёстой. LCS-ээс ялгаатай.
  • Үсэг ижил үед ч +1 нэмэх. Ижил бол үйлдэл хэрэггүй.
  • min({a, b, c}) гэж хаалтыг мартах. min хоёр тоо л авдаг, гурвыг бол {} дотор бичнэ.

Хязгаарын тохиолдол

  • Хоёр string ижил: хариу 0.
  • Нэг string хоосон: хариу нь нөгөөгийнх нь урт.
  • Нийтлэг үсэггүй, урт нь ижил: хариу нь урт, бүх үсгийг солино.

Өөрийгөө шалга

  1. "KITTEN"-ийг "SITTING" болгоход хэдэн үйлдэл хэрэгтэй вэ?

    Хариу харах

    3: K-г S-ээр солих, E-г I-гаар солих, G нэмэх.

  2. "A"-г "XYZ" болгоход хэдэн үйлдэл вэ?

    Хариу харах

    3: A-г X-ээр солиод Y, Z нэмнэ.

  3. Үсэг өөр үед хүснэгтийн аль гурван нүдийг уншдаг вэ?

    Хариу харах

    Дээрх, зүүн, зүүн дээд нүдийг.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1."HORSE"-ийг "ROS" болгох хүснэгтийг бөглөөд хариуг ол.

    Hint харах

    Эхний багана 0, 1, 2, 3, 4, 5, эхний мөр 0, 1, 2, 3.

    Хариу ба тайлбар

    Хариу 3: H-ийг R-аар солих, R-ыг устгах, E-г устгах.

  2. 2.Солих үйлдэл 2 гэж үнэтэй болсон. Кодыг өөрчлөөд "SUNNY" → "SNOWY"-ийн хариуг ол.

    Hint харах

    Зөвхөн зүүн дээд нүдэнд нэмэх тоо өөрчлөгдөнө.

    Хариу ба тайлбар

    min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2). Хариу 4. Энэ нь n + m − 2 · LCS = 5 + 5 − 2 · 3-тай тэнцүү.

  3. 3.Тоог биш, хийх үйлдлүүдийг өөрсдийг нь хэвлэдэг болго.

    Hint харах

    dp[n][m]-ээс эхлээд аль хөршөөс ирснийг хараад буцаж алх.

    Хариу ба тайлбар

    Үсэг ижил бол i--, j--. Үгүй бол dp[i][j] == dp[i - 1][j] + 1 бол устгах, dp[i][j - 1] + 1 бол нэмэх, бусад үед солих. Үйлдлүүдийг урвуу дарааллаар хэвлэнэ.

Жишээ

Оролт

SUNNY
SNOWY

Гаралт

3