โปรแกรมหาลำดับการดำเนินการแปลงสตริงหนึ่งเป็นอีกสตริงใน C++

ให้สตริง S และ T หาลำดับการดำเนินการสั้นที่สุดแปลง S เป็น T (Insert '+' หรือ Delete '-')

ตัวอย่าง: S="xxxy", T="xxyy" → ["x","x","-x","y","+y"] วาง x,x ลบ x ตัวที่ 3 วาง y เพิ่ม y

ขั้นตอนการแก้ปัญหา (DP + Path Reconstruction)

1. DP[i][j] = ขั้นตอนน้อยสุดแปลง S[i..] เป็น T[j..]
   • ถ้า S[i]==T[j]: dp[i][j] = dp[i+1][j+1]
   • Delete: 1 + dp[i+1][j]
   • Insert: 1 + dp[i][j+1]
   • เลือก min
2. Reconstruct path: จาก dp[0][0] ย้อนกลับดูว่าเลือก operation ไหน

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int dp[505][505];

class Solution {
public:
    int help(int i, int j, string& S, string& T) {
        if (i == S.size() && j == T.size()) return dp[i][j] = 0;
        if (i == S.size()) return dp[i][j] = 1 + help(i, j+1, S, T);
        if (j == T.size()) return dp[i][j] = 1 + help(i+1, j, S, T);
        if (dp[i][j] != -1) return dp[i][j];
        int dontDo = (S[i]==T[j]) ? help(i+1,j+1,S,T) : 1e5;
        int del = 1 + help(i+1, j, S, T);
        int ins = 1 + help(i, j+1, S, T);
        return dp[i][j] = min({dontDo, del, ins});
    }
    void getPath(int i, int j, string& S, string& T, int cur, vector<string>& ret) {
        if (cur==0 && i==S.size() && j==T.size()) return;
        if (i
อินพุต
"xxxy", "xxyy"
เอาต์พุต
x x -x y +y