Market›String-to-string correction problem
Company Profile

String-to-string correction problem

In computer science, the string-to-string correction problem refers to determining the minimum cost sequence of edit operations necessary to change one string into another. Each type of edit operation has its own cost value. A single edit operation may be changing a single symbol of the string into another, deleting a symbol, or inserting a new symbol.

Extension
The extended variant of the problem includes a new type of edit operation: swapping any two adjacent symbols, with a cost of WS. This version can be solved in polynomial time under certain restrictions on edit operation costs. Robert A. Wagner (1975) showed that the general problem is NP-complete. In particular, he proved that when WI C = WD = ∞ and 0 S < ∞ (or equivalently, changing and deletion are not permitted), the problem is NP-complete. == References ==
Source: Wikipedia ↗
tickerdossier.comtickerdossier.substack.com