strings.min_cost_string_conversion

Algorithm for calculating the most cost-efficient sequence for converting one string into another. The only allowed operations are — Cost to copy a character is copy_cost — Cost to replace a character is replace_cost — Cost to delete a character is delete_cost — Cost to insert a character is insert_cost

Attributes

m

Functions

assemble_transformation(→ list[str])	Assembles the transformations based on the ops table.
compute_transform_tables(→ tuple[list[list[int]], ...)	Finds the most cost efficient sequence

Module Contents

strings.min_cost_string_conversion.assemble_transformation(ops: list[list[str]], i: int, j: int) → list[str]

Assembles the transformations based on the ops table.

>>> ops = [['0', 'Ic', 'Iu', 'It'],
...        ['Dc', 'Cc', 'Iu', 'It'],
...        ['Da', 'Da', 'Rau', 'Rat'],
...        ['Dt', 'Dt', 'Rtu', 'Ct']]
>>> x = len(ops) - 1
>>> y = len(ops[0]) - 1
>>> assemble_transformation(ops, x, y)
['Cc', 'Rau', 'Ct']

>>> ops1 = [['0']]
>>> x1 = len(ops1) - 1
>>> y1 = len(ops1[0]) - 1
>>> assemble_transformation(ops1, x1, y1)
[]

strings.min_cost_string_conversion.compute_transform_tables(source_string: str, destination_string: str, copy_cost: int, replace_cost: int, delete_cost: int, insert_cost: int) → tuple[list[list[int]], list[list[str]]]

Finds the most cost efficient sequence for converting one string into another.

>>> costs, operations = compute_transform_tables("cat", "cut", 1, 2, 3, 3)
>>> costs[0][:4]
[0, 3, 6, 9]
>>> costs[2][:4]
[6, 4, 3, 6]
>>> operations[0][:4]
['0', 'Ic', 'Iu', 'It']
>>> operations[3][:4]
['Dt', 'Dt', 'Rtu', 'Ct']

>>> compute_transform_tables("", "", 1, 2, 3, 3)
([[0]], [['0']])

strings.min_cost_string_conversion.m