allcoding1_official: post #18935 — TG.ME

ALallcoding1_official@allcoding1_official · 82K subscribersOpen in TelegramOpen

import java.util.*;

class Main {
public static int solve(String word1, String word2) {
int n = word1.length();
int m = word2.length();

final int INF = 1_000_000;

int[][][] dp = new int[n + 1][m + 1][2];

for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j][0] = INF;
dp[i][j][1] = INF;
}
}

dp[n][m][0] = 0;
dp[n][m][1] = 0;

for (int i = n; i >= 0; i--) {
for (int j = m; j >= 0; j--) {
for (int p = 0; p < 2; p++) {

if (i == n && j == m) continue;

int ans = INF;


if (i < n) {
ans = Math.min(ans, 1 + dp[i + 1][j][p ^ 1]);
}


if (j < m) {
ans = Math.min(ans, 1 + dp[i][j + 1][p ^ 1]);
}


if (i < n && j < m) {
char c = word1.charAt(i);
if (p == 1) {
c = (char) ('a' + (c - 'a' + 13) % 26);
}

if (c == word2.charAt(j))
ans = Math.min(ans, dp[i + 1][j + 1][p]);
else
ans = Math.min(ans, 1 + dp[i + 1][j + 1][p]);
}

dp[i][j][p] = ans;
}
}
}

return dp[0][0][0];
}

t.me/allcoding1_official/18935

August 2, 2026 2K