C ++中的一个编辑距离

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有两个字符串s和t；我们必须检查它们是否相距一个编辑距离。一个编辑距离具有三种类型-

  • 在s中插入一个字符以得到t

  • 从s删除字符以获得t

  • 替换字符s以获得t

因此，如果输入类似于s =“ ab”，t =“ acb”，则输出将为True

为了解决这个问题，我们将遵循以下步骤-

  • n：= s的大小，m：= t的大小

  • 如果n <m，则-

    • 返回isOneEditDistance(t,s)

  • 对于初始化i：= 0，当i <m时，更新（将i增加1），执行-

    • 如果n与m相同，则-

    • 当s从索引0到(i)的子字符串与t从索引0到(i-1)的子字符串相同时，返回true

    • 当s的从索引0到(i)的子字符串与t的从索引0到(i)的子字符串相同时，返回true

    • 如果s [i]不等于t [i]，则-

    • 当m +1与n相同时返回true

    例 

    让我们看下面的实现以更好地理解-

    #include <bits/stdc++.h>
    using namespace std;
    class Solution {
    public:
       bool isOneEditDistance(string s, string t) {
          int n = s.size();
          int m = t.size();
          if (n < m) {
             return isOneEditDistance(t, s);
          }
          for (int i = 0; i < m; i++) {
             if (s[i] != t[i]) {
                if (n == m) {
                   return s.substr(i + 1) == t.substr(i + 1);
                }
                return s.substr(i + 1) == t.substr(i);
             }
          }
          return m + 1 == n;
       }
    };
    main(){
       Solution ob;
       cout << (ob.isOneEditDistance("ab", "acb"));
    }

    输入项

    s = "ab", t = "acb"

    输出结果

    1

    以上是 C ++中的一个编辑距离 的全部内容， 来源链接： utcz.com/z/338058.html

    回到顶部