Поиск минимальных ходов, необходимых для того, чтобы сделать 2 строки равными

Это вопрос одной из задач онлайн-кодирования (которая завершилась).
Мне просто нужна логика для этого, как подойти.

Проблема:
У нас есть две строки A и B с тем же супер набором символов. Нам нужно изменить эти строки, чтобы получить две равные строки. В каждом шаге мы можем выполнить одну из следующих операций:

1. swap two consecutive characters of a string  
2. swap the first and the last characters of a string

Перемещение может выполняться в любой строке.
Что такое минимальное количество ходов, которое нам нужно, чтобы получить две равные строки?

Формат ввода и ограничения:
Первая и вторая строки ввода содержат две строки A и B. Гарантируется, что надмножество их символов равно.

1 <= length(A) = length(B) <= 2000
All the input characters are between 'a' and 'z'

Формат вывода:
Напечатайте минимальное количество ходов на единственную строку вывода

Sample input:
aab
baa

Sample output:
1

Объяснение:
Поменяйте первый и последний символ строки aab, чтобы преобразовать ее в baa. Теперь две строки равны.

EDIT: Вот моя первая попытка, но я получаю неправильный вывод. Может ли кто-нибудь вести меня, что не так в моем подходе.

int minStringMoves(char* a, char* b) {
    int length, pos, i, j, moves=0;
    char *ptr;
    length = strlen(a);

    for(i=0;i<length;i++) {
        // Find the first occurrence of b[i] in a
        ptr = strchr(a,b[i]);
        pos = ptr - a;

        // If its the last element, swap with the first
        if(i==0 && pos == length-1) {
            swap(&a[0], &a[length-1]);
            moves++;
        }
        // Else swap from current index till pos
        else {
            for(j=pos;j>i;j--) {
                swap(&a[j],&a[j-1]);
                moves++;
            }
        }

        // If equal, break
        if(strcmp(a,b) == 0)
            break;       
   }

   return moves;
}

Ответ 1

Взгляните на этот пример:

aaaaaaaaab
abaaaaaaaa

Ваше решение: 8

aaaaaaaaab -> aaaaaaaaba -> aaaaaaabaa -> aaaaaabaaa -> aaaaabaaaa -> 
aaaabaaaaa -> aaabaaaaaa -> aabaaaaaaa -> abaaaaaaaa

Правильное решение: 2

aaaaaaaaab -> baaaaaaaaa -> abaaaaaaaa

Вы должны проверить, приведет ли обмен в другом направлении к лучшему результату.

Но иногда вы также разрушаете предыдущую часть строки. например:

caaaaaaaab
cbaaaaaaaa

caaaaaaaab -> baaaaaaaac -> abaaaaaaac

Вам нужна еще одна свопа, чтобы вернуть "c" на первое место.

Правильный алгоритм, вероятно, еще более сложный, но теперь вы можете видеть, что не так в вашем решении.

Ответ 2

Алгоритм A * может работать для этой проблемы.

Начальная node будет исходной строкой.
Цель node будет целевой строкой.
Каждый дочерний элемент node будет всеми возможными преобразованиями этой строки.
Текущая стоимость g(x) - это просто количество преобразований до сих пор.
Эвристический h(x) составляет половину числа символов в неправильном положении.

Так как h(x) допустимо (поскольку одно преобразование не может помещать более двух символов в их правильные позиции), путь к целевой строке даст наименьшее количество преобразований.

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

Обратите внимание, что существует много сходства между node братьями и сестрами (его родительскими дочерними элементами) и его дочерними элементами. Таким образом, вы можете просто вычислить все преобразования исходной строки и, оттуда, просто скопировать и пересчитать данные с измененными символами.

Ответ 3

Вы можете использовать динамическое программирование . Перейдите по всем возможностям свопинга, сохранив все промежуточные результаты вместе с минимальным количеством шагов, которые заставили вас туда добраться. Фактически, вы собираетесь рассчитать минимальное количество шагов для каждой возможной целевой строки, которую можно получить, применяя заданные правила для числа раз. После того, как вы все вычислите, вы можете напечатать минимальное количество шагов, необходимых для перехода к целевой строке. Здесь пример кода в JavaScript и его использование для примеров "aab" и "baa" :

function swap(str, i, j) {
   var s = str.split("");
   s[i] = str[j];
   s[j] = str[i];
   return s.join("");
}

function calcMinimumSteps(current, stepsCount)
{
   if (typeof(memory[current]) !== "undefined") {
      if (memory[current] > stepsCount) {
          memory[current] = stepsCount;
      } else if (memory[current] < stepsCount) {
          stepsCount = memory[current];
      }
   } else {
      memory[current] = stepsCount;
      calcMinimumSteps(swap(current, 0, current.length-1), stepsCount+1);
      for (var i = 0; i < current.length - 1; ++i) {
          calcMinimumSteps(swap(current, i, i + 1), stepsCount+1);
      }
   }
}

var memory = {};
calcMinimumSteps("aab", 0);
alert("Minimum steps count: " + memory["baa"]);

Ответ 4

Вот рубиновая логика для этой проблемы, скопируйте этот код в файл rb и выполните.

str1 = "education" #Sample first string
str2 = "cnatdeiou" #Sample second string

moves_count = 0
no_swap = 0
count = str1.length - 1

def ends_swap(str1,str2)    
    str2 = swap_strings(str2,str2.length-1,0)
    return str2
end

def swap_strings(str2,cp,np)
    current_string = str2[cp]
    new_string = str2[np]
    str2[cp] = new_string
    str2[np] = current_string
    return str2
end

def consecutive_swap(str,current_position, target_position)
    counter=0
    diff = current_position > target_position ? -1 : 1
    while current_position!=target_position
        new_position = current_position + diff
        str = swap_strings(str,current_position,new_position)
        # p "-------"
        # p "CP: #{current_position}   NP: #{new_position} TP: #{target_position}  String: #{str}"
        current_position+=diff
        counter+=1
    end
    return counter,str
end

while(str1 != str2 && count!=0)
    counter = 1
    if str1[-1]==str2[0]
        # p "cross match"
        str2 = ends_swap(str1,str2)
    else
        # p "No match for #{str2}-- Count: #{count}, TC: #{str1[count]}, CP: #{str2.index(str1[count])}"
        str = str2[0..count]
        cp = str.rindex(str1[count])
        tp = count
        counter, str2 = consecutive_swap(str2,cp,tp)
        count-=1        
    end
    moves_count+=counter    
    # p "Step: #{moves_count}"
    # p str2
end

p "Total moves: #{moves_count}"

Пожалуйста, не стесняйтесь предлагать какие-либо улучшения в этом коде.

Ответ 5

Попробуйте этот код. Надеюсь, это поможет вам.

открытый класс TwoStringIdentical {

static int lcs(String str1, String str2, int m, int n) {
    int L[][] = new int[m + 1][n + 1];
    int i, j;

    for (i = 0; i <= m; i++) {
        for (j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;

            else if (str1.charAt(i - 1) == str2.charAt(j - 1))
                L[i][j] = L[i - 1][j - 1] + 1;

            else
                L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
        }
    }

    return L[m][n];
}

static void printMinTransformation(String str1, String str2) {
    int m = str1.length();
    int n = str2.length();
    int len = lcs(str1, str2, m, n);
    System.out.println((m - len)+(n - len));
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    String str1 = scan.nextLine();
    String str2 = scan.nextLine();
    printMinTransformation("asdfg", "sdfg");
}

}