Edit Distance - Classic Problems | Repovive

CLS6. Edit Distance

1s256 MB

Given two strings $s$ and $t$ , find the minimum number of operations to convert $s$ into $t$ .

Allowed operations:

\begin{array}{l} s \\ t \end{array}

$ops$

Input

kat
cat

Explanation

For this input, the required output is 1.

Output

Input

sitting
kitten

Explanation

For this input, the required output is 3.

Output

Input

flaw
lawn

Explanation

For this input, the required output is 2.

Output

1s256 MB

Given two strings $s$ and $t$ , find the minimum number of operations to convert $s$ into $t$ .

Allowed operations:

\begin{array}{l} s \\ t \end{array}

$ops$

Input

kat
cat

Explanation

For this input, the required output is 1.

Output

Input

sitting
kitten

Explanation

For this input, the required output is 3.

Output

Input

flaw
lawn

Explanation

For this input, the required output is 2.

Output