Editační vzdálenost řetězců
Completion requirements
Opened: Wednesday, 18 March 2020, 12:00 AM
Due: Wednesday, 1 April 2020, 11:59 PM
Editační vzdálenost mezi dvěma řetězci je definována jako nejmenší počet operací, jejichž aplikováním na první řetězec dostaneme druhý řetězec, kde povolené operace jsou:
- smazání jednoho znaku,
- vložení jednoho znaku,
- přepsání znaku na jiný.
Máme zadané dva řetězce A a B (ne nutně stejně dlouhé). Spočtěte jejich editační vzdálenost.
Pokud vám to pomůže, můžete předpokládat, že abeceda má konstantní velikost, není to však potřeba.
Nápověda: pokud vám úloha přijde podobná předchozí, vězte, že to není náhoda :-)