NC403. 编辑距离为一
描述
示例1
输入:
"nowcoder","nawcoder"
输出:
true
示例2
输入:
"nowcoder","nawcader"
输出:
false
C 解法, 执行用时: 8ms, 内存消耗: 924KB, 提交时间: 2022-07-30
#include<stdbool.h>
bool editdistance(char* s, char* t ) {
int h = strlen( s);
int H = strlen(t);
if (h - H >= 2 || H - h >= 2)
return false;
int l = 0, r = h - 1;
int L = 0, R = H - 1;
while (l < h && L < H && s[l] == t[L]) {
l += 1, L += 1;
}
while (R > L && r > l && s[r] == t[R]) {
R -= 1;
r -= 1;
}
if (r - l == 0 || R - L == 0) {
return true;
}
return false;
}
C 解法, 执行用时: 8ms, 内存消耗: 928KB, 提交时间: 2022-06-28
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param t string字符串
* @return bool布尔型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
#include <stdbool.h>
bool editdistance(char* s, char* t ) {
int sLen = strlen(s), tLen = strlen(t);
if (sLen - tLen > 1 || sLen - tLen < -1) {
return false;
}
int i = 0, j = 0, flag = 1;
while(i < sLen && j < tLen) {
if (s[i] == t[j]) {
i++;
j++;
} else if (s[i] != t[j]) {
if (sLen == tLen) {
if (flag == 1) {
flag = 0;
i++;
j++;
} else {
return false;
}
} else if (sLen < tLen) {
if (flag == 1) {
flag = 0;
j++;
} else {
return false;
}
} else if (sLen > tLen) {
if (flag == 1) {
flag = 0;
i++;
} else {
return false;
}
}
}
}
if (i == sLen && j == tLen && flag == 0) {
return true;
} else if ((i != sLen || j != tLen) && flag == 1) {
return true;
} else {
return false;
}
}
C++ 解法, 执行用时: 8ms, 内存消耗: 1124KB, 提交时间: 2022-07-30
class Solution {
public:
bool editdistance(string s, string t) {
int h = s.size();
int H = t.size();
if (h - H >= 2 || H - h >= 2)
return false;
int l = 0, r = h - 1;
int L = 0, R = H - 1;
while (l < h && L < H && s[l] == t[L]) {
l += 1, L += 1;
}
while (R > L && r > l && s[r] == t[R]) {
R -= 1;
r -= 1;
}
if (r - l == 0 || R - L == 0) {
return true;
}
return false;
}
};
C++ 解法, 执行用时: 8ms, 内存消耗: 1172KB, 提交时间: 2022-05-06
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param t string字符串
* @return bool布尔型
*/
bool editdistance(string s, string t) {
// write code here
int len1 = s.size();
int len2 = t.size();
if(len1- len2 >= 2 || len2 - len1 >= 2)
return false;
int i_left = 0, i_right = s.size() - 1;
int j_left = 0, j_right = t.size() - 1;
while (i_left < len1 && j_left < len2 && s[i_left] == t[j_left]) {
i_left += 1, j_left += 1;
}
while (j_right > j_left && i_right > i_left && s[i_right] == t[j_right]) {
j_right -= 1;
i_right -= 1;
}
if (i_right - i_left == 0 || j_right - j_left == 0) {
return true;
}
return false;
}
};
C++ 解法, 执行用时: 8ms, 内存消耗: 1180KB, 提交时间: 2022-07-02
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param t string字符串
* @return bool布尔型
*/
bool editdistance(string s, string t) {
// write code here
int lens=s.size();
int lent=t.size();
if(abs(lens-lent)>1)
{
return false;
}
if(lens==lent)//长度相同，只能修改一个字符
{
int cnt=0;
for(int i=0;i<lens;i++)
{
if(s[i]!=t[i])
{
cnt++;
}
if(cnt>1)
{
return false;
}
}
if(cnt==0)//完全相等，编辑距离为0
{
return false;
}
}
else //长度短的添加一个字符
{
if(lens<lent)
{
int cnt=0;
for(int i=0;i<lens;i++)
{
if(cnt==0)
{
if(s[i]!=t[i])
{
cnt++;
i--;
}
}
else
{
if(s[i]!=t[i+1])
{
return false;
}
}
}
}
else
{
int cnt=0;
for(int i=0;i<lent;i++)
{
if(cnt==0)
{
if(s[i]!=t[i])
{
cnt++;
i--;
}
}
else
{
if(s[i+1]!=t[i])
{
return false;
}
}
}
}
}
return true;
//return help(s,t);
}
bool help(string s,string t)
{
//压缩空间复杂度
vector<int> dp(t.size()+1,0);
for(int j=1;j<=t.size();j++)
{
dp[j]=j;
}
for(int i=1;i<=s.size();i++)
{
auto tmp=dp;
dp[0]=i;
for(int j=1;j<=t.size();j++)
{
if(s[i-1]==t[j-1])
{
dp[j]=tmp[j-1];
}
else
{
dp[j]=min(tmp[j-1],min(tmp[j],dp[j-1]))+1;
}
}
}
return dp[t.size()]==1;
}
};