G. Левенштейний зай

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Хоёр тэмдэгт мөрийн хоорондох Левенштейний зай нь нэг тэмдэгт мөрийг нөгөө тэмдэгт мөр болгон өөрчлөх үед гарах засварлах үйл ажиллагаануудын нийт өртөг юм. Зөвшөөрөгдсөн засварлах ажиллагаанууд нь:

  • Орлуулга: нэг үсгийг өөр үсгээр солих өртөг нь Англи хэлний цагаан толгойн байрлалуудын хоорондох зөрүү.
  • Үсэг нэмэх болон хасах: тэмдэгт мөрөнд үсэг нэмэх болон хасах өртөг нь Англи хэлний цагаан толгойн байрлал дахь тоо.

Таньд $2$ тэмдэгт мөр өгсөн бол Левенштейний зайг ол.

Оролт

Хоёр мөрөнд мөр бүрд Латин жижиг үсэгнээс бүтсэн тэмдэгт мөр байна. Тэмдэгт мөр болгон $1$-ээс $100$-ийн хооронд урттай байна (энд $1$ болон $100$ нь орно).

Гаралт

Тэмдэгт мөрүүдийн хоорондох Левенштейний зай болох нэг бүхэл тоог хэвлэнэ.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
arc
bug
Гаралт
8
Оролт
dome
drone
Гаралт
19

Тэмдэглэл

Эхний жишээнд "a"-г "b"-ээр (өртөг $1$), "r"-г "u"-аар (өртөг $3$), "c"-г "g"-ээр (өртөг $4$) солино.

Хоёр дахь жишээнд "r" (өртөг $18$) үсгийг оруулан бас "m" үсгийг "n"-ээр (өртөг $1$) солино.

Сэтгэгдлүүдийг ачааллаж байна...