This repository has been archived by the owner on Dec 7, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathStringEditDistanceOne.java
107 lines (92 loc) · 2.5 KB
/
StringEditDistanceOne.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
package com.ematrix;
public class StringEditDistanceOne {
static boolean isEditDistanceOne(String s1,
String s2) {
// Find lengths of given strings
int m = s1.length(), n = s2.length();
// If difference between lengths is
// more than 1, then strings can't
// be at one distance
if (Math.abs(m - n) > 1)
return false;
int count = 0; // Count of edits
int i = 0, j = 0;
while (i < m && j < n)
{
// If current characters don't match
if (s1.charAt(i) != s2.charAt(j))
{
if (count == 1)
return false;
// If length of one string is
// more, then only possible edit
// is to remove a character
if (m > n)
i++;
else if (m< n)
j++;
else // Iflengths of both strings
// is same
{
i++;
j++;
}
// Increment count of edits
count++;
}
else // If current characters match
{
i++;
j++;
}
}
// If last character is extra
// in any string
if (i < m || j < n)
count++;
return count == 1;
}
// driver code
static boolean isEditDistanceTwo(String s1,
String s2) {
int i =0;
int j =0;
int n1=s1.length();
int n2=s2.length();
if(Math.abs(n1-n2)>1){
return false;
}
int count=0;
while(i<n1 && j<n2){
if(s1.charAt(i)==s2.charAt(j)){
j++;
i++;
}else{
if(count==1){return false;}
if(n1==n2){
j++;
i++;
}
if(n1>n2){
i++;
}
if(n1<n2){
j++;
}
count++;
}
}
if (i < n1 || j < n2)
count++;
return count == 1;
}
public static void main (String[] args)
{
String s1 = "gfg";
String s2 = "gfgr";
if(isEditDistanceTwo(s1, s2))
System.out.print("Yes");
else
System.out.print("No");
}
}