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

Условие

Метод, который проверяет, можно ли получить одну строку из другой, совершив ровно одну из следующих операций:

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

Примеры: "a" → "b" → true "ab" → "b" → true "ab" → "cb" → true "ab" → "ba" → false

public boolean editing(String s1, String s2) {
    // реализация
}

Ответ

Сравнивайте строки двумя указателями и разрешите одно несовпадение. При разной длине пропускайте символ только в более длинной строке, при равной — в обеих.

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 code points нужен другой способ обхода.