-
Notifications
You must be signed in to change notification settings - Fork 14
/
StringTransformation.java
70 lines (60 loc) · 2.41 KB
/
StringTransformation.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
package by.andd3dfx.string;
import org.apache.commons.lang3.StringUtils;
/**
* <pre>
* Написать метод (класс и импорты не нужны) на вход которого приходит две строки.
* На выходе надо проверить можно ли получить одну строку из другой за 1 исправление:
* - замена одного символа в одной строке
* - вставка/удаление одного символа из одной строки
*
* Примеры тестовых сценариев:
* first = "a", second = "b" -> true
* first = "ab", second = "b" -> true
* first = "ab", second = "cb" -> true
* first = "ab", second = "ba" -> false
* first = "abcd", second = "abd" -> true
* </pre>
*
* @see <a href="https://youtu.be/GOSWr4jHng8">Video solution</a>
*/
public class StringTransformation {
public static boolean couldTransform(String first, String second) {
char[] s1 = first.toCharArray();
char[] s2 = second.toCharArray();
var len1 = s1.length;
var len2 = s2.length;
if (Math.abs(len1 - len2) > 1) { // Lengths differ significantly
return false;
}
if (len1 == len2) { // Same lengths
var count = 0;
for (var i = 0; i < len1; i++) {
if (s1[i] != s2[i]) {
count++;
if (count > 1) {
return false;
}
}
}
return true;
}
// Lengths differ by 1 - so need to remove/add one character
var pos = 0;
while (pos < len1 && pos < len2 && s1[pos] == s2[pos]) {
pos++;
}
if (pos + 1 < len1 && pos < len2 && s1[pos + 1] == s2[pos]) {
return remainingPartsShouldBeEqual(first, pos + 1, second, pos);
}
if (pos < len1 && pos + 1 < len2 && s1[pos] == s2[pos + 1]) {
return remainingPartsShouldBeEqual(first, pos, second, pos + 1);
}
return true;
}
private static boolean remainingPartsShouldBeEqual(String first, int from1, String second, int from2) {
return StringUtils.equals(
first.substring(from1),
second.substring(from2)
);
}
}