华为OD机试2025C卷-字符串变换最小次数[100分]（ Java _ Python3 _ C++ _ C语言 _ JsNode _ Go）实现100%通过率

个人主页深夜coding算法 专栏系列2026年华为最新OD机试题库详解 一次订阅永久解锁 | 持续更新100篇 | 6语言全覆盖文章目录❄️前言☀️一题目描述 题目名称 题目内容 输入描述 输出描述 示例☀️二解题思路☀️三代码实现CJavaPython3C语言JavaScriptGo☀️四复杂度分析⭐ 五易错点坑1初始化边界坑2三种操作对应关系共勉❄️前言字符串变换最小次数——编辑距离Levenshtein Distance。DP经典题递推公式就一句dp[i][j] 三种操作的最小值。☀️一题目描述 题目名称字符串变换最小次数 题目内容给定两个字符串word1和word2。每次可以对word1执行以下任一操作插入一个字符、删除一个字符、替换一个字符。求将word1变成word2所需的最少操作次数。 输入描述第一行字符串 word1第二行字符串 word2长度不超过 500。 输出描述输出一个整数最少操作次数。 示例输入 horse ros 输出 3 说明horse→rorse(替换h) →rose(删r) →ros(删e)3步☀️二解题思路dp[i][j]word1前i个字符 变 word2前j个字符 的最少操作数。若w1[i-1] w2[j-1]dp[i][j] dp[i-1][j-1]否则dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])☀️三代码实现C#includeiostream#includestring#includevectorusingnamespacestd;intmain(){string w1,w2;getline(cin,w1);getline(cin,w2);intnw1.size(),mw2.size();vectorvectorintdp(n1,vectorint(m1));for(inti0;in;i)dp[i][0]i;for(intj0;jm;j)dp[0][j]j;for(inti1;in;i)for(intj1;jm;j){if(w1[i-1]w2[j-1])dp[i][j]dp[i-1][j-1];elsedp[i][j]1min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]});}coutdp[n][m]endl;}Javaimportjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);Stringw1sc.nextLine(),w2sc.nextLine();intnw1.length(),mw2.length();int[][]dpnewint[n1][m1];for(inti0;in;i)dp[i][0]i;for(intj0;jm;j)dp[0][j]j;for(inti1;in;i)for(intj1;jm;j){if(w1.charAt(i-1)w2.charAt(j-1))dp[i][j]dp[i-1][j-1];elsedp[i][j]1Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]));}System.out.println(dp[n][m]);}}Python3w1input().strip()w2input().strip()n,mlen(w1),len(w2)dp[[0]*(m1)for_inrange(n1)]foriinrange(n1):dp[i][0]iforjinrange(m1):dp[0][j]jforiinrange(1,n1):forjinrange(1,m1):ifw1[i-1]w2[j-1]:dp[i][j]dp[i-1][j-1]else:dp[i][j]1min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])print(dp[n][m])C语言#includestdio.h#includestring.h#defineMIN3(a,b,c)((a)(b)?((a)(c)?(a):(c)):((b)(c)?(b):(c)))intmain(){charw1[512],w2[512];gets(w1);gets(w2);intnstrlen(w1),mstrlen(w2),dp[512][512];for(inti0;in;i)dp[i][0]i;for(intj0;jm;j)dp[0][j]j;for(inti1;in;i)for(intj1;jm;j){if(w1[i-1]w2[j-1])dp[i][j]dp[i-1][j-1];elsedp[i][j]1MIN3(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]);}printf(%d\n,dp[n][m]);}JavaScriptconst[w1,w2]require(fs).readFileSync(0,utf-8).trim().split(\n);constnw1.length,mw2.length;constdpArray.from({length:n1},(_,i)[i,...Array(m).fill(0)]);dp[0]Array.from({length:m1},(_,j)j);for(leti1;in;i)for(letj1;jm;j)dp[i][j]w1[i-1]w2[j-1]?dp[i-1][j-1]:1Math.min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]);console.log(dp[n][m]);Gopackagemainimport(bufio;fmt;os)funcmain(){sc:bufio.NewScanner(os.Stdin)sc.Scan();w1:sc.Text()sc.Scan();w2:sc.Text()n,m:len(w1),len(w2)dp:make([][]int,n1)fori:rangedp{dp[i]make([]int,m1);dp[i][0]i}forj:0;jm;j{dp[0][j]j}fori:1;in;i{forj:1;jm;j{ifw1[i-1]w2[j-1]{dp[i][j]dp[i-1][j-1]}else{dp[i][j]1min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])}}}fmt.Println(dp[n][m])}☀️四复杂度分析指标数值时间复杂度O(N*M)空间复杂度O(N*M)⭐ 五易错点坑1初始化边界dp[i][0]i删除i次dp[0][j]j插入j次。坑2三种操作对应关系dp[i-1][j]删除dp[i][j-1]插入dp[i-1][j-1]替换。共勉编辑距离是DP面试题里的Hello World背也要背下来。关于本专栏一次订阅永久解锁全部100篇真题详解6语言全覆盖Java | Python3 | C | C语言 | JsNode | Go