cho.sh

Minimum Edit 2

Compute the minimum number of insertions, deletions, replacements, and adjacent swaps needed to turn string A into string B, with both strings up to length 1000.

Medium7Dynamic programmingStringImplementationBrute forceInterviewNo attempts yetTime limit2sMemory limit512 MB

Problem

Given two strings A and B, the minimum edit problem asks for the smallest number of operations that turn A into B.

Four operations apply to A.

  1. Insertion: insert one character at some position of A.
  2. Deletion: remove one character from A.
  3. Replacement: change one character of A into a different character.
  4. Swap: exchange two adjacent characters of A.

The operations are applied one after another to the current string.

Write a program that reads two strings and computes the minimum number of edits.

Input

The first line contains the string A and the second line contains the string B. Both strings consist of lowercase letters only, and the length of each is between 1 and 1000.

Output

Print the minimum number of edits on the first line.