In this problem, you need to implement a function that calculates the Optimal String Alignment (OSA) distance between two given strings. The OSA distance represents the minimum number of edits required to transform one string into another. The allowed edit operations are:
- Insert a character
- Delete a character
- Substitute a character
- Transpose two adjacent characters
Each of these operations costs 1 unit.
Your task is to find the minimum number of edits needed to convert the first string (s1) into the second string (s2).
For example, the OSA distance between the strings caper and acer is 2: one deletion (removing "p") and one transposition (swapping "a" and "c").
Examples
Example 1:
Input:
source = "butterfly"
target = "dragonfly"
distance = OSA(source, target)
print(distance)Output:
6Explanation: The OSA distance between the strings "butterfly" and "dragonfly" is 6. The minimum number of edits required to transform the source string into the target string is 6.
Starter Code
def OSA(source: str, target: str) -> int:
# Your code here
pass
Python3
ReadyLines: 1Characters: 0
Ready