Как решить, какой подход нужно использовать для написания алгоритмов?

Question

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

• Добавление луковицы в определенном месте. • Извлечь лампу из местоположения. • Замена лампы на другую лампу разного цвета.

Учитывая две цветовые последовательности двух различных цепей ламп, найдите минимальный номер. операций, необходимых для этого преобразования. (Предположим, что каждый цвет может быть представлен символом, и, следовательно, цветовая последовательность цепочки ламп может быть представлена ​​как последовательность символов или строка.) Входные/выходные данные Вход: • Первая последовательность цветов (строка A) • Вторая цвет последовательности (строка в)

Выход: Минимальное Количество операций, необходимых для преобразования первой цепи лампы во второй (целое число)

Примеры Input1: "asdfgh" input2: "sdfgh"

Выход: 1

Input1: "х" input2: "ASDF"

Выход: 4

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

Answer 1

Из википедии:

int LevenshteinDistance(string s, string t) 
{ 
    // degenerate cases 
    if (s == t) return 0; 
    if (s.Length == 0) return t.Length; 
    if (t.Length == 0) return s.Length; 

    // create two work vectors of integer distances 
    int[] v0 = new int[t.Length + 1]; 
    int[] v1 = new int[t.Length + 1]; 

    // initialize v0 (the previous row of distances) 
    // this row is A[0][i]: edit distance for an empty s 
    // the distance is just the number of characters to delete from t 
    for (int i = 0; i < v0.Length; i++) 
     v0[i] = i; 

    for (int i = 0; i < s.Length; i++) 
    { 
     // calculate v1 (current row distances) from the previous row v0 

     // first element of v1 is A[i+1][0] 
     // edit distance is delete (i+1) chars from s to match empty t 
     v1[0] = i + 1; 

     // use formula to fill in the rest of the row 
     for (int j = 0; j < t.Length; j++) 
     { 
      var cost = (s[i] == t[j]) ? 0 : 1; 
      v1[j + 1] = Minimum(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost); 
     } 

     // copy v1 (current row) to v0 (previous row) for next iteration 
     for (int j = 0; j < v0.Length; j++) 
      v0[j] = v1[j]; 
    } 

    return v1[t.Length]; 
}