#include <iostream> #include <cstdlib> #include <string> using namespace std; int minDistance(string word1,string word2) { //在此处写入代码 } 本关任务： 编写一个函数来实现最短编辑距离计算方法。 编辑距离算法被数据科学家广泛应用，是用作机器翻译和语音识别评价标准的基本算法。 给你两个单词word1和word2(均为小写英文单词)，请返回将word1转换成 word2所使用的最少操作数（编辑距离）。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符 例如： word1 = "horse", word2 = "ros" 编辑距离=3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
```cpp #include <iostream> #include <cstdlib> #include <string> #include <vector> using namespace std; int minDistance(string word1, string word2) { int m = word1.length(); int n = word2.length(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 初始化第一行和第一列 for (int i = 0; i <= m; i++) { dp[i][0] = i; } for (int j = 0; j <= n; j++) { dp[0][j] = j; } // 填充dp数组 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1[i - 1] == word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1); } } } return dp[m][n]; } ``` [2025-11-12 14:55:49 | AI问答 | 311点数解答]
相关提问
- [字节豆包] #include <iostream> #include <cstdlib> #include <string> using namespace std; int minDistance(string word1,string word2) { //在此处写入代码 } 本关任务： 编写一个函数来实现最短编辑距离计算方法。 编辑距离算法被数据科学家广泛应用，是用作机器翻译和语音识别评价标准的基本算法。 给你两个单词word1和word2(均为小写英文单词)，请返回将word1转换成 word2所使用的最少操作数（编辑距离）。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符 例如： word1 = "horse", word2 = "ros" 编辑距离=3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')（311点数解答 | 2025-11-12 14:55:49）25
- [讯飞星火] 快速排序：# include< iostream>using namespace std;# include< stdlib. h># include< time. h>const int n =10;const int min= 10;const int max=99;int getrand( int min, int max){return ( rand()%( max-min+1)+ min);}void set( int r[], int n){int i;for(i=0;i<n;i++)r[i]=getrand(min, max);}void show( int r[], int n){int i;for(i=0;i<n;i++)cout << r[i]<<" ";cout << endl;}int partition( int r[], int i, int j){//由你完成}void quicksort( int r[], int i, int j){//由你完成}int main(){srand( time(0));int a[n];set(a, n);cout<<"（710点数解答 | 2024-11-14 10:44:25）275
- [阿里通义] 快速排序：# include< iostream>using namespace std;# include< stdlib. h># include< time. h>const int n =10;const int min= 10;const int max=99;int getrand( int min, int max){return ( rand()%( max-min+1)+ min);}void set( int r[], int n){int i;for(i=0;i<n;i++)r[i]=getrand(min, max);}void show( int r[], int n){int i;for(i=0;i<n;i++)cout << r[i]<<" ";cout << endl;}int partition( int r[], int i, int j){//由你完成}void quicksort( int r[], int i, int j){//由你完成}int main(){srand( time(0));int a[n];set(a, n);cout<<"（951点数解答 | 2024-11-14 10:46:29）260
- [字节豆包] 快速排序：# include< iostream>using namespace std;# include< stdlib. h># include< time. h>const int n =10;const int min= 10;const int max=99;int getrand( int min, int max){return ( rand()%( max-min+1)+ min);}void set( int r[], int n){int i;for(i=0;i<n;i++)r[i]=getrand(min, max);}void show( int r[], int n){int i;for(i=0;i<n;i++)cout << r[i]<<" ";cout << endl;}int partition( int r[], int i, int j){//由你完成}void quicksort( int r[], int i, int j){//由你完成}int main(){srand( time(0));int a[n];set(a, n);cout<<"（472点数解答 | 2024-11-14 10:51:44）249
- [字节豆包] #include<iostream> using namespace std;#include<stdlib.h>#include<time.h> const int n =10; const int min =10; const int max =99; int getrand(int min, int max) { return (rand() % (max - min +1) + min); void set(int r[], int n){ int i; for(i = 0; i< n; i++) r[i] = getrand(min,max); void show(int r[], int n) { int i; for (i = 0; i<n;i++) cout << r[i] << ""; cout << endl;}void sift(int r[],int m,int k){ } void heapsort(intr[], int n){ //由你完成 int main(){ srand(time(0)); int a[n]; set(a,n); cout <<"原序（417点数解答 | 2024-11-28 11:20:23）312
- [阿里通义] 修改代码#include <iostream> #include <string> #include <unordered_map> #include <ctime> #include <openssl/sha.h> #include <openssl/aes.h> #include <openssl/rand.h> #include <io.h> #include<process.h> #include <winsock2.h> // 处理可能未定义的socklen_t类型 #ifndef socklen_t typedef int socklen_t; #endif #define port 8080 #define otp_valid_time 120 // otp有效时间为2分钟 // 用户结构体 struct user { std::string username; std::string hashed_password; std::string otp; time_t otp_time; }; // 存储用户的哈希表 std::uno（465点数解答 | 2024-11-23 20:41:37）177
- [DeepSeek] using communication_protocols; using FTS_F02391A; using NLog; using ScottPlot.Plottable; using Sunny.UI; using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Threading; using System.Threading.Tasks; using System.Windows.Forms; namespace 窗体界面设计 { public partial class FormHome : UIPage { private readonly DataLogger Log1;//波形图数据记录器 bool bViewSlide = false（562点数解答 | 2025-07-09 16:57:56）134
- [字节豆包] #include<iostream> using namespace std;#include<stdlib.h>#include<time.h> const int n =10; const int min =10; const int max =99; int getrand(int min, int max) { return (rand() % (max - min +1) + min); void set(int r[], int n){ int i; for(i = 0; i< n; i++) r[i] = getrand(min,max); void show(int r[], int n) { int i; for (i = 0; i<n;i++) cout << r[i] << ""; cout << endl; void heapsort(intr[], int n){ //由你完成 int main(){ srand(time(0)); int a[n]; set(a,n); cout <<"原序列:"; show(a,n); cout <<"新序列:\n"; h（684点数解答 | 2024-11-28 11:21:15）259
- [阿里通义] #include<iostream> using namespace std;#include<stdlib.h>#include<time.h> const int n=10; const int min=10; const int max=99; int getrand(inmin,int max) { return (rand()%(max-min+1)+min); void set(int r[],int n) { int i; for(i=0; i<n; i++) r[i]=getrand(min,max); void show(intr[],int n){ int i; for(i=0; i<n; i++) cout<<r[i]<<""; cout<<endl; void insertsort(int r[],int n){//由你完成} int main() { srand(time(0)); int a[n]; set(a,n); cout<<"原序列:"; show(a,n); cout<<"新序列: \n; insertsort(a,n);//show(a,n);（690点数解答 | 2024-10-31 10:11:20）263
- [字节豆包] #include<iostream> using namespace std;#include<stdlib.h>#include<time.h> const int n=10; const int min=10; const int max=99; int getrand(inmin,int max) { return (rand()%(max-min+1)+min); void set(int r[],int n) { int i; for(i=0; i<n; i++) r[i]=getrand(min,max); void show(intr[],int n){ int i; for(i=0; i<n; i++) cout<<r[i]<<""; cout<<endl; void insertsort(int r[],int n){//由你完成} int main() { srand(time(0)); int a[n]; set(a,n); cout<<"原序列:"; show(a,n); cout<<"新序列: \n; insertsort(a,n);//show(a,n);（147点数解答 | 2024-10-31 10:29:38）269
- [讯飞星火] #include<iostream> using namespace std;#include<stdlib.h>#include<time.h> const int n=10; const int min=10; const int max=99; int getrand(inmin,int max) { return (rand()%(max-min+1)+min); void set(int r[],int n) { int i; for(i=0; i<n; i++) r[i]=getrand(min,max); void show(intr[],int n){ int i; for(i=0; i<n; i++) cout<<r[i]<<""; cout<<endl; void insertsort(int r[],int n){//由你完成} int main() { srand(time(0)); int a[n]; set(a,n); cout<<"原序列:"; show(a,n); cout<<"新序列: \n; insertsort(a,n);//show(a,n);（703点数解答 | 2024-10-31 10:35:24）256
- [阿里通义] #include<iostream> using namespace std;#include<stdlib.h>#include<time.h> const int n=10; const int min=10; const int max=99; int getrand(inmin,int max) { return (rand()%(max-min+1)+min); void set(int r[],int n) { int i; for(i=0; i<n; i++) r[i]=getrand(min,max); void show(intr[],int n){ int i; for(i=0; i<n; i++) cout<<r[i]<<""; cout<<endl; void shellsort(int r[],int n){//由你完成} int main() { srand(time(0)); int a[n]; set(a,n); cout<<"原序列:"; show(a,n); cout<<"新序列: \n; shellsort(a,n);//show(a,n); re（593点数解答 | 2024-10-31 10:39:07）296