java-algorithims/StringEditDistanceOne.java at main · faraimtb/java-algorithims · GitHub

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
packagecom.ematrix;

publicclassStringEditDistanceOne {

staticbooleanisEditDistanceOne(Strings1,
Strings2) {
// Find lengths of given strings
intm = 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)
returnfalse;

intcount = 0; // Count of edits

inti = 0, j = 0;
while (i < m && j < n)
 {
// If current characters don't match
if (s1.charAt(i) != s2.charAt(j))
 {
if (count == 1)
returnfalse;

// If length of one string is
// more, then only possible edit
// is to remove a character
if (m > n)
i++;
elseif (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++;

returncount == 1;
 }
// driver code

staticbooleanisEditDistanceTwo(Strings1,
Strings2) {
inti =0;
intj =0;
intn1=s1.length();
intn2=s2.length();
if(Math.abs(n1-n2)>1){
returnfalse;
 }
intcount=0;
while(i<n1 && j<n2){
if(s1.charAt(i)==s2.charAt(j)){
j++;
i++;
 }else{
if(count==1){returnfalse;}
if(n1==n2){
j++;
i++;
 }
if(n1>n2){
i++;
 }
if(n1<n2){
j++;
 }
count++;
 }

 }
if (i < n1 || j < n2)
count++;


returncount == 1;
 }
publicstaticvoidmain (String[] args)
 {
Strings1 = "gfg";
Strings2 = "gfgr";
if(isEditDistanceTwo(s1, s2))
System.out.print("Yes");
else
System.out.print("No");
 }
}