1.5 - One Away
There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away. EXAMPLE pale, ple -> true pales, pale -> true pale, bale -> true pale, bake -> false

Algorithm:

1
#include <stdio.h>
2
#include <stdlib.h>
3
#include <string.h>
4
#include <stdbool.h>
5
6
bool OneAway(char* str1, char* str2){
7
8
int len1 = strlen(str1);
9
int len2 = strlen(str2);
10
int i = 0, j = 0;
11
12
for(i = 0, j = 0; i < len1 && j < len2; i++, j++){
13
if(str1[i] != str2[j]){
14
break;
15
}
16
}
17
18
if( i == len1 && j == len2){
19
return true;
20
}
21
22
int e_i = len1 - 1, e_j = len2 -1;
23
for(e_i = len1 - 1, e_j = len2 -1; e_i >= i && e_j >= j; e_i--, e_j--){
24
if(str1[e_i] != str2[e_j]){
25
break;
26
}
27
}
28
29
printf("i = %d, j = %d, ei = %d, ej = %d\n", i, j, e_i, e_j);
30
31
return (e_i - i <= 1) && (e_j - j <= 1);
32
}
33
Copied!

Test:

1
int main(){
2
3
4
char testStr1[100] = "pale";
5
char testStr2[100] = "ple";
6
printf("OneAway = %d\n", OneAway(testStr1, testStr2));
7
8
return 0;
9
}
Copied!
Copy link