Loading problem...
You are given two strings, source and target, both consisting of lowercase English letters. Your objective is to determine the minimum number of single-character operations required to convert source into target.
You are permitted to perform the following three operations on the source string:
Each operation has a uniform cost of 1. Your goal is to find the minimum total cost (i.e., the minimum number of operations) to transform source into target.
This is a classic dynamic programming problem that measures the "distance" between two strings—often referred to as the transformation distance or the minimum cost to make two strings identical through elementary edits.
source = "horse"
target = "ros"3One optimal transformation sequence: • horse → rorse (substitute 'h' with 'r') • rorse → rose (remove the second 'r') • rose → ros (remove 'e') Total operations: 3
source = "intention"
target = "execution"5One optimal transformation sequence: • intention → inention (remove 't') • inention → enention (substitute 'i' with 'e') • enention → exention (substitute first 'n' with 'x') • exention → exection (substitute 'n' with 'c') • exection → execution (insert 'u' before 't') Total operations: 5
source = "abc"
target = "abc"0Both strings are already identical, so no operations are required.
Constraints