資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中的一編輯距離
假設我們有兩個字串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)，執行：
如果s[i]不等於t[i]，則：
如果n等於m，則：
如果s從索引0到(i)的子串與t從索引0到(i)的子串相同，則返回true
如果s從索引0到(i)的子串與t從索引0到(i-1)的子串相同，則返回true
如果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
更新於：2020年11月18日
122 次瀏覽
廣告