Dynamic Programming for Strings | Dataford Interview Questions

Your question is Dynamic Programming for Strings. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

qXR may receive OCR text containing character substitutions, missing characters, or adjacent character swaps. Given a source string and a target string, compute the minimum cost to align the source with the target.

Allowed operations are:

Insert one character into the source, consuming one target character.
Delete one source character.
Replace one source character with one target character. Matching characters cost zero.
Transpose two adjacent source characters when they equal the next two target characters in reverse order.

Each operation has a caller-provided non-negative cost. The alignment proceeds from left to right, so a transposition consumes exactly two source and two target characters.

Formal Specification

Implement minimum_alignment_cost(source, target, insert_cost, delete_cost, replace_cost, transpose_cost). Return an integer representing the minimum alignment cost. The inputs are strings and integer operation costs.

Constraints

0 <= len(source), len(target) <= 2000
0 <= insert_cost, delete_cost, replace_cost, transpose_cost <= 10^6
Strings contain lowercase English letters
A transposition consumes exactly two adjacent characters from each string

Function Signature

def minimum_alignment_cost(source, target, insert_cost, delete_cost, replace_cost, transpose_cost):