FilesExpand file tree

 master

/

OneEditDistance.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

54 lines (50 loc) · 1.28 KB

 master

/

OneEditDistance.java

Copy path

Top

File metadata and controls

• Code
• Blame

54 lines (50 loc) · 1.28 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

package string;

/**

* Created by gouthamvidyapradhan on 09/12/2017.

*

* <p>Given two strings S and T, determine if they are both one edit distance apart.

*/

public class OneEditDistance {

/**

* Main method

*

* @param args

* @throws Exception

*/

public static void main(String[] args) throws Exception {

System.out.println(new OneEditDistance().isOneEditDistance("abxd", "adxb"));

}

public boolean isOneEditDistance(String s, String t) {

if (Math.abs(s.length() - t.length()) > 1 || s.equals(t)) return false;

if (s.length() > t.length()) {

return hasDiffOne(s, t, false);

} else if (t.length() > s.length()) {

return hasDiffOne(t, s, false);

} else {

return hasDiffOne(s, t, true);

}

}

private boolean hasDiffOne(String s, String t, boolean sameLength) {

int count = 0, i = 0, j = 0;

for (int l1 = s.length(), l2 = t.length(); i < l1 && j < l2; ) {

if (s.charAt(i) == t.charAt(j)) {

i++;

j++;

} else {

if (count > 0) return false;

count++;

if (sameLength) {

i++;

j++;

} else {

i++;

}

}

}

if (i == j) {

return true;

} else {

return (s.charAt(s.length() - 1) == t.charAt(t.length() - 1));

}

}

}