C++: Khoảng cách chỉnh sửa là 1 phải không?
Giải phóng thời gian, khai phóng năng lực
Bài toán
Khoảng cách chỉnh sửa giữa hai chuỗi ký tự a và b là số lần ít nhất xoá ký tự, thêm ký tự, hay thay đổi một ký tự a thành ký tự b (hoặc ngược lại).
Hãy viết một hàm để đánh giá 2 chuỗi ký tự có phải là có khoảng cách chỉnh sửa là 1 hay không (tương đương với việc xác định có thể sinh ra chuỗi thứ 1 từ chuỗi thứ 2 bằng cách xóa hoặc thêm bớt hoặc thay đổi 1 ký tự hay không).
Ví dụ:
• Chuỗi ký tự 1 là "abcde", chuỗi ký tự 2 là "abcd" => Trả về: true
• Chuỗi ký tự 1 là "abce", chuỗi ký tự 2 là "abcd" => Trả về: true
• Chuỗi ký tự 1 là "abade", chuỗi ký tự 2 là "abcd" => Trả về: false
Đáp án
#include<iostream> using namespace std; bool chinhSua(string s1,string s2){ int n=s1.length(); int m=s2.length(); if((m-n)>=2||(n-m)>=2){ return false; } else if(n-m==0){ int count=0; for(int i=0;i<n; i++){ if(s1[i]!=s2[i]){ count++; } } if(count==1){ return true; } return false; } else if(n-m==1){ int count=0; for(int i=0;i<m; i++){ if(s1[i]!=s2[i]){ count++; } } if(count==0){ return true; } else{ int vt=0; for(int i=0;i<m; i++){ if(s1[i]!=s2[i]){ vt=i; break; } } for(int i=vt+1;i<n; i++){ s1[i-1]=s1[i]; } s1[n-1]='\0'; for(int i=0;i<m; i++){ if(s1[i]!=s2[i]){ return false; } } return true; } } else if(m-n==1){ int count=0; for(int i=0;i<n; i++){ if(s1[i]!=s2[i]){ count++; } } if(count==0){ return true; } else{ int vt=0; for(int i=0;i<n; i++){ if(s1[i]!=s2[i]){ vt=i; break; } } for(int i=vt+1;i<m; i++){ s2[i-1]=s2[i]; } s2[n-1]='\0'; for(int i=0;i<n; i++){ if(s1[i]!=s2[i]){ return false; } } return true; } } return 0; } main(){ string s1; string s2; getline(cin,s1); getline(cin,s2); if(chinhSua(s1,s2)) cout<<"Hai chuoi co khoang cach chinh sua la 1"; else cout<<"Hai chuoi co khoang cach chinh sua khac 1"; return 0; }
Giải phóng thời gian, khai phóng năng lực