Changing a String (Codeforces 56D)
Tags: DP, dp

There is a string s, consisting of capital Latin letters. Let's denote its current length as |s|. During one move it is allowed to apply one of the following operations to it:   INSERT pos ch — insert a letter ch in the string s in the position pos (1 ≤ pos ≤ |s| + 1, A ≤ ch ≤ Z). The letter ch becomes the pos-th symbol of the string s, at that the letters shift aside and the length of the string increases by 1.  DELETE pos — delete a character number pos (1 ≤ pos ≤ |s|) from the string s. At that the letters shift together and the length of the string decreases by 1.  REPLACE pos ch — the letter in the position pos of the line s is replaced by ch (1 ≤ pos ≤ |s|, A ≤ ch ≤ Z). At that the length of the string does not change. Your task is to find in which minimal number of moves one can get a t string from an s string. You should also find the sequence of actions leading to the required results.

Input: The first line contains s, the second line contains t. The lines consist only of capital Latin letters, their lengths are positive numbers from 1 to 1000.

Output: In the first line print the number of moves k in the given sequence of operations. The number should be the minimal possible one. Then print k lines containing one operation each. Print the operations in the format, described above. If there are several solutions, print any of them.


Sample Inputs:
ABA
ABBBA

ACCEPTED
WRONGANSWER

Sample Outputs:
2
INSERT 3 B
INSERT 4 B

10
REPLACE 1 W
REPLACE 2 R
REPLACE 3 O
REPLACE 4 N
REPLACE 5 G
REPLACE 6 A
INSERT 7 N
INSERT 8 S
INSERT 9 W
REPLACE 11 R

Solution (Python):
def answer(first, second):
    dp = [[0 for _ in range(len(first) + 1)] for _ in range(len(second) + 1)]
    for i in range(len(first) - 1, -1, -1):
        dp[-1][i] = dp[-1][i + 1] + 1
    for i in range(len(second) - 1, -1, -1):
        dp[i][-1] = dp[i + 1][-1] + 1
    for i in range(len(second) - 1, -1, -1):
        for j in range(len(first) - 1, -1, -1):
            if first[j] == second[i]:
                dp[i][j] = dp[i + 1][j + 1]
            else:
                dp[i][j] = min(dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1]) + 1
    print(dp[0][0])
    (start, end) = (0, 0)
    result = []
    while (start, end) != (len(second), len(first)):
        if start == len(second):
            print('DELETE ' + str(start + 1))
            (start, end) = (start, end + 1)
        elif end == len(first):
            print('INSERT ' + str(start + 1) + ' ' + second[start])
            (start, end) = (start + 1, end)
        else:
            newmin = min(dp[start + 1][end + 1], dp[start + 1][end], dp[start][end + 1])
            if newmin != dp[start][end]:
                if dp[start + 1][end + 1] <= dp[start + 1][end] and dp[start + 1][end + 1] <= dp[start][end + 1]:
                    print('REPLACE ' + str(start + 1) + ' ' + second[start])
                    (start, end) = (start + 1, end + 1)
                elif dp[start + 1][end] <= dp[start + 1][end + 1] and dp[start + 1][end] <= dp[start][end + 1]:
                    print('INSERT ' + str(start + 1) + ' ' + second[start])
                    (start, end) = (start + 1, end)
                else:
                    print('DELETE ' + str(start + 1))
                    (start, end) = (start, end + 1)
            else:
                (start, end) = (start + 1, end + 1)
first = input()
second = input()
answer(first, second)

Solution (Python):
import heapq
from collections import defaultdict, Counter
graph = defaultdict(set)

def listinput():
    return list(map(int, input().split()))

def editDistance(word1, word2):
    dp = [[i] + [0] * len(word1) for i in range(len(word2) + 1)]
    dp[0] = [i for i in range(len(word1) + 1)]
    for j in range(1, len(word2) + 1):
        for i in range(1, len(word1) + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[j][i] = dp[j - 1][i - 1]
            else:
                dp[j][i] = min(dp[j - 1][i - 1], dp[j - 1][i], dp[j][i - 1]) + 1
    return dp

def solve(s, t):
    table = editDistance(s, t)
    (i, j) = (len(t), len(s))
    operations = []
    print(table[-1][-1])
    while table[i][j] > 0:
        cur = table[i][j]
        replace = table[i - 1][j - 1]
        delete = table[i][j - 1]
        insert = table[i - 1][j]
        if insert < cur and insert <= delete and (insert <= replace):
            operations.append('INSERT ' + str(i) + ' ' + t[i - 1])
            i -= 1
        elif delete < cur and delete <= insert and (delete <= replace):
            operations.append('DELETE ' + str(i + 1))
            j -= 1
        elif replace < cur and replace <= insert and (replace <= delete):
            operations.append('REPLACE ' + str(i) + ' ' + t[i - 1])
            i -= 1
            j -= 1
        else:
            i -= 1
            j -= 1
    for op in reversed(operations):
        print(op)
s = input()
t = input()
solve(s, t)

Solution (Python):
def editDistance(s, t):
    sl = len(s)
    tl = len(t)
    for i in range(tl + 1):
        dp[0][i] = i
    for i in range(sl + 1):
        dp[i][0] = i
    for i in range(1, sl + 1):
        for j in range(1, tl + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
    return dp[-1][-1]

def trace(s, t):
    n = len(s)
    m = len(t)
    while n > 0 and m > 0:
        if s[n - 1] == t[m - 1]:
            n -= 1
            m -= 1
        elif dp[n - 1][m - 1] == dp[n][m] - 1:
            print('REPLACE', n, t[m - 1])
            n -= 1
            m -= 1
        elif dp[n - 1][m] == dp[n][m] - 1:
            print('DELETE', n)
            n -= 1
        else:
            print('INSERT', n + 1, t[m - 1])
            m -= 1
    while m > 0:
        print('INSERT', 1, t[m - 1])
        m -= 1
    while n > 0:
        print('DELETE', n)
        n -= 1
s = input()
t = input()
global dp
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
print(editDistance(s, t))
trace(s, t)