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


Đăng ký nhận thông báo về những video mới nhất

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;
}

Nếu bạn có điều thắc mắc, bạn hãy comment cho V1Study để được giải đáp.
Bài viết này được chia sẻ bởi LongDT. Nếu bạn muốn chia sẻ bài viết, bạn hãy Đăng ký làm thành viên!
« Prev
Next »
Copied !!!