Edit Distance

Given two strings S and T. Return the minimum number of operations required to convert S to T. The possible operations are permitted:

1. Insert a character at any position of the string.
2. Remove any character from the string.
3. Replace any character from the string with any other character.

Input Format

First-line consist of first-string S Second-line consists of second-string T.

Output Format

The output consists of a single line, The number of operations required to convert S to T.

Example 1:

    geek
    gesek
Output:
    1
Explanation:
    One operation is required
    inserting 's' between two 'e's of str1.

Example 2:

Input :
    gfg
    gfg
Output:
    0
Explanation:
    Both strings are the same.

Constraints:

• 1 ≤ Length of both strings ≤ 100
• Expected Time Complexity: O(|s|*|t|)
• Expected Space Complexity: O(|s|*|t|)