Проверить, можно ли сравнять две строки одной заменой или добавлением символа

63. Проверить, можно ли сделать строки одинаковыми за одно изменение

Условие задачи:
Даны две строки. Необходимо вернуть true, если их можно сделать одинаковыми, выполнив не более одного изменения:

заменить один символ;
добавить один символ в одну из строк.

Если требуется больше одного изменения, нужно вернуть false.

Код:

public boolean isOneEditAway(String first, String second) {
    // код тут
}

Примеры:

"cat", "cut"  → true
"cat", "cats" → true
"cat", "dog"  → false

Спойлеры к решению

Подсказки

💡 Если разница длин больше одного, сразу верни false.
💡 При равной длине допустимо не более одного несовпадающего символа.
💡 При разнице длин в один символ используй два указателя.
💡 При первом несовпадении сдвигай указатель только в длинной строке.

Решение

public boolean isOneEditAway(
        String first,
        String second
) {
    if (first == null || second == null) {
        return false;
    }

    if (Math.abs(first.length() - second.length()) > 1) {
        return false;
    }

    if (first.length() == second.length()) {
        return canReplaceOneCharacter(first, second);
    }

    String shorter = first.length() < second.length()
            ? first
            : second;

    String longer = first.length() < second.length()
            ? second
            : first;

    return canAddOneCharacter(shorter, longer);
}

private boolean canReplaceOneCharacter(
        String first,
        String second
) {
    int differences = 0;

    for (int i = 0; i < first.length(); i++) {
        if (first.charAt(i) != second.charAt(i)) {
            differences++;

            if (differences > 1) {
                return false;
            }
        }
    }

    return true;
}

private boolean canAddOneCharacter(
        String shorter,
        String longer
) {
    int shorterIndex = 0;
    int longerIndex = 0;
    boolean differenceFound = false;

    while (shorterIndex < shorter.length()
            && longerIndex < longer.length()) {

        if (shorter.charAt(shorterIndex)
                == longer.charAt(longerIndex)) {
            shorterIndex++;
            longerIndex++;
            continue;
        }

        if (differenceFound) {
            return false;
        }

        differenceFound = true;
        longerIndex++;
    }

    return true;
}

При одинаковой длине строк проверяется возможность одной замены. При разнице длин в один символ допускается один пропуск в более длинной строке.

Одинаковые строки также возвращают true, поскольку требуется не более одного изменения.

Временная сложность — O(n), дополнительная память — O(1).