Всем привет, надеюсь, ваша неделя началась отлично! Для сегодняшней проблемы с алгоритмом я собираюсь написать функцию, которая может видеть, сколько шагов было предпринято для редактирования строки, и если был предпринят только один шаг, функция вернет 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; }
В любом случае, если вы, ребята, узнали что-то интересное или думаете, что решение довольно крутое, нажмите кнопку аплодисментов! Если у вас есть лучшие способы решить эту проблему, не стесняйтесь оставить ответ или связаться со мной, спасибо!