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

Question

Я должен написать функцию, которая принимает два слова (строки) в качестве аргументов и определяет, можно ли преобразовать первое слово во второе слово, используя только одно преобразование первого порядка.

• Преобразования первого порядка изменяют только одну букву в слове

• Допустимые преобразования: вставка, удаление и замена

  • вставка = вставить букву в любомпозиция в слове
  • удалить = удалить букву из любой позиции в слове
  • заменить = заменить букву другой

Какие-либо предложения?Любые примеры Java были бы великолепны!

Answer 1

Подумайте: если вам разрешено только одно преобразование, то разница в длине между словами «до» и «после» должна дать вам очень сильный намек на то, какое из этих трех преобразований имеет какой-либо шанс на успех , Точно так же вы можете сразу увидеть, какие преобразования будут просто невозможны.

Как только вы определились с тем, какое преобразование, остальная часть проблемы становится работой для Brute Force Man и его напарника Looping Lady.

Answer 2

Это похоже на домашнюю работу, поэтому я не собираюсь давать вам ответ, но каждый раз, когда вы подходите к такой проблеме, лучше всего начать набрасывать некоторые идеи.Разбейте проблему на более мелкие куски, и тогда ее будет легче решить.

Например, давайте посмотрим на операцию вставки.Чтобы вставить букву, что это будет делать с длиной слова, в которое мы вставляем букву?Увеличить или уменьшить?Если мы увеличиваем длину слова, а длина этого нового слова не равна длине слова, которое мы пытаемся сопоставить, то что это говорит вам?Таким образом, одно условие здесь заключается в том, что если вы собираетесь выполнить операцию вставки первого слова, чтобы оно соответствовало второму слову, то есть известная длина, которой должно быть первое слово.

Вы можете применить аналогичныеидеи для двух других операций.

Так что, как только вы установите эти условия, становится легче разработать алгоритм для решения проблемы.

Важная вещь в любом типе назначения, как это, состоит в том, чтобыпродумать этоНе просто спрашивайте кого-нибудь, «дайте мне код», вы не узнаете ничего подобного.Когда вы застряли, можно попросить о помощи (но покажите нам, что вы уже сделали), но цель домашней работы - научиться.

Answer 3

Если вам нужно проверить, есть ли одно и ровно одно редактирование от s1 до s2, то это очень легко проверить с помощью простого линейного сканирования.

• Если оба имеютодинаковой длины, тогда должен быть ровно один индекс, в котором эти два значения отличаются
  • Они должны согласовываться с общим самым длинным префиксом, затем пропускают ровно один символ из обоих, затем они должны согласовывать общий суффикс
• Если один короче другого, тогда разница в длине должна составлять ровно один
  • Они должны совпадать с общим длинным префиксом, тогда пропускается ровно один символ из более длинногоВо-первых, они должны согласовать общий суффикс

Если вы также разрешите редактирование нуля от s1 до s2, просто проверьте, являются ли они equal.

Вот реализация Java:

static int firstDifference(String s1, String s2, int L) {
    for (int i = 0; i < L; i++) {
        if (s1.charAt(i) != s2.charAt(i)) {
            return i;
        }
    }
    return L;
}
static boolean oneEdit(String s1, String s2) {
    if (s1.length() > s2.length()) {
        return oneEdit(s2, s1);
    }
    final int L = s1.length();
    final int index = firstDifference(s1, s2, L);
    if (s1.length() == s2.length() && index != L) {
        return s1.substring(index+1).equals(s2.substring(index+1));
    } else if (s2.length() == L + 1) {
        return s1.substring(index).equals(s2.substring(index+1));
    } else {
        return false;
    }
}

Затем мы можем проверить это следующим образом:

    String[][] tests = {
        { "1", "" },
        { "123", "" },
        { "this", "that" },
        { "tit", "tat" },
        { "word", "sword" },
        { "desert", "dessert" },
        { "lulz", "lul" },
        { "same", "same" },
    };
    for (String[] test : tests) {
        System.out.printf("[%s|%s] = %s%n",
            test[0], test[1], oneEdit(test[0], test[1])
        );
    }

Это печатает (, как видно на ideone.com):

[1|] = true
[123|] = false
[this|that] = false
[tit|tat] = true
[word|sword] = true
[desert|dessert] = true
[lulz|lul] = true
[same|same] = false

Answer 4

Вы можете использовать расстояние Левенштейна и разрешить только расстояния 1 (что означает, что один символ должен быть изменен). Есть несколько реализаций, просто Google "Levenshtein Java" или около того.

Другой "не такой умный", но работающий предмет - старая добрая грубая сила. Просто попробуйте каждую ситуацию с каждым символом, и вы получите то, что хотите. : -)