Всем привет, надеюсь, ваша неделя началась отлично! Для сегодняшней проблемы с алгоритмом я собираюсь написать функцию, которая может видеть, сколько шагов было предпринято для редактирования строки, и если был предпринят только один шаг, функция вернет true. Шаги, которые вы можете выполнить со строкой:

  • Изменение одного персонажа
  • Удаление одного персонажа
  • Вставка одного символа

Вот пример:

Input: pale, bale
Output: True
Input: bake, pale
Output: False

Для начала я подумал о том, как сравнить две строки и что будет означать их длина. Например, если в строке заменен символ, она останется той же длины, а вставка или удаление будут отличаться на единицу. Итак, теперь проблема заключается в написании функций, которые могут сравнивать каждую строку на основе двух приведенных выше случаев.

Таким образом, для случая, когда длина строк одинакова, мы можем проверить символ каждой строки, а затем иметь троичную логическую переменную, которая будет принимать значение true, если было сделано одно изменение, и обратно в значение false, если было сделано другое изменение. Вот как это выглядит в коде:

function oneEditReplace(s1, s2) {
    let foundDifference = false;
    for (let i = 0; i < s1.length; i++) {
        if(s1[i] != s2[i]) {
            if (foundDifference)
                return false;
        }
        foundDifference = true;
    }
}

Теперь, для следующего случая, у меня есть итератор, просматривающий каждую строку для сравнения каждого символа, а затем, в основном, если итераторы не равны друг другу в конце, функция вернет false, иначе функция вернет true. Вот как это выглядит в коде:

function oneEditInsert(s1, s2) {
    let index1 = 0;
    let index2 = 0;
    while (index2 < s2.length && index1 < s1.length){
        if (s1[index1] != s2[index2]) {
            if (index1 != index2)
                return false;
            index2++
        } else {
              index1++;
              index2++;
        }
    }
    return true;
}

Теперь, когда эти функции определены, стало намного проще проверять, находятся ли строки на расстоянии одного редактирования друг от друга. Вот код, который на самом деле сравнивает две строки:

function oneEditAway(first, second) {
    if (first.length == second.length)
        return oneEditReplace(first, second);
    if ((first.length) + 1 == second.length)
        return oneEditInsert(first, second);
    if ((first.length) - 1 == second.length)
        return oneEditInsert(second, first);
    return false;
}

В любом случае, если вы, ребята, узнали что-то интересное или думаете, что решение довольно крутое, нажмите кнопку аплодисментов! Если у вас есть лучшие способы решить эту проблему, не стесняйтесь оставить ответ или связаться со мной, спасибо!