C++: Khoảng cách chỉnh sửa là 1 phải không?

Các khóa học qua video:
Python SQL Server PHP C# Lập trình C Java HTML5-CSS3-JavaScript
Học trên YouTube <76K/tháng. Đăng ký Hội viên
Viết nhanh hơn - Học tốt hơn
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;
}
» Tiếp: Solution bài tập phần vòng lặp
« Trước: Deque
Các khóa học qua video:
Python SQL Server PHP C# Lập trình C Java HTML5-CSS3-JavaScript
Học trên YouTube <76K/tháng. Đăng ký Hội viên
Viết nhanh hơn - Học tốt hơn
Giải phóng thời gian, khai phóng năng lực
Copied !!!