【題解】ZeroJudge e828: 3.猴子打字遊戲 (Typing)

#include <iostream>
#include <cstring>
using namespace std;
string s1, s2;

int editDistance(){
    int len1 = (int) s1.length();
    int len2 = (int) s2.length();
  
    int dp[2][len1 + 1];
    memset(dp, 0, sizeof dp);
  
    //s2 為空字串
    for (int i = 0; i <= len1; i++)
        dp[0][i] = i * 2; //add
  
    for (int i = 1; i <= len2; i++) {
        for (int j = 0; j <= len1; j++) {
            if (j == 0) //s1 為空字串
                dp[i % 2][j] = i * 2; //delete
            else if (s1[j - 1] == s2[i - 1]) {
                dp[i % 2][j] = dp[(i - 1) % 2][j - 1];
            } else {
                dp[i % 2][j] = min(dp[(i - 1) % 2][j] + 2,
                                   min(dp[i % 2][j - 1] + 2,
                                       dp[(i - 1) % 2][j - 1] + 3));
            }
        }
    }
    return dp[len2 % 2][len1];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> s1;
    int mn = 1e9, idx = 0;
    for (int i=1; i<=3; i++){
        cin >> s2;
        int dis = editDistance();
        if (dis <= mn){
            mn = dis;
            idx = i;
        }
    }
    cout << idx << " " << mn << "\n";
    return 0;
}

import sys

def editDistance():
    len1 = len(s1)
    len2 = len(s2)
    dp = [[0 for j in range(len1+1)] for i in range(2)]
    for i in range(len1+1):
        dp[0][i] = i * 2 # add
        
    for i in range(1, len2+1):
        for j in range(len1+1):
            if j == 0:
                dp[i%2][j] = i * 2
            elif s1[j-1] == s2[i-1]:
                dp[i%2][j] = dp[(i-1)%2][j-1]
            else:
                dp[i%2][j] = min([
                        dp[(i-1)%2][j] + 2,
                        dp[i%2][j-1] + 2,
                        dp[(i-1)%2][j-1] + 3,
                        ])
    return dp[len2 % 2][len1]

lines = sys.stdin.readlines()
s1 = lines[0].strip()
mn = 1000000000
idx = 0
for i in range(1, 4):
    s2 = lines[i].strip()
    dis = editDistance();
    if (dis <= mn):
        mn = dis
        idx = i

print(idx, mn)