Определение возможности преобразования строки за одно редактирование

Условие

Требуется реализовать функцию (без объявления класса и импортов), принимающую две строки и возвращающую логическое значение, указывающее, можно ли получить одну строку из другой, используя ровно одно из следующих действий:

• замена одного символа;
• вставка или удаление одного символа.

Примеры входных данных и ожидаемых результатов:

first = "a", second = "b"   -> true
first = "ab", second = "b" -> true
first = "ab", second = "cb" -> true
first = "ab", second = "ba" -> false

public boolean editing(String s1, String s2) {
}

Ответ

Разница длин не должна превышать единицу. На первом несовпадении пропускайте один символ в длинной строке либо в обеих равных по длине; второе несовпадение означает false.

public boolean editing(String s1, String s2) {
    if (s1 == null || s2 == null) throw new IllegalArgumentException();
    if (Math.abs(s1.length() - s2.length()) > 1) return false;
    int i = 0, j = 0, edits = 0;
    while (i < s1.length() && j < s2.length()) {
        if (s1.charAt(i) == s2.charAt(j)) { i++; j++; }
        else {
            if (++edits > 1) return false;
            if (s1.length() >= s2.length()) i++;
            if (s2.length() >= s1.length()) j++;
        }
    }
    if (i < s1.length() || j < s2.length()) edits++;
    return edits == 1;
}

Одинаковые строки дают false: требуется ровно одна правка, изменяющая строку. Время O(n+m), память O(1); символом здесь считается UTF-16 char, а не произвольный Unicode grapheme cluster.