如何决定需要使用哪种方法来编写算法？

Question

某灯饰店老板有几条不同类型的灯串，这些灯串由不同颜色的灯泡按不同的顺序组成。除此之外，他还收藏了大量各种颜色的灯泡。灯泡链通过其灯泡的颜色顺序来识别。他想通过以下任一方式将一种类型的灯泡链转变为另一种类型的灯泡链：

• 在某个位置添加灯泡。 • 从某个位置取下灯泡。 • 用另一个不同颜色的灯泡更换灯泡。

给定两个不同灯串的两种颜色序列，找到最小编号。进行此转换所需的操作。 （假设每种颜色都可以用一个字符表示，因此灯泡链的颜色序列可以表示为字符序列或字符串。） 输入/输出规格 输入： • 第一个颜色序列（字符串 A） • 第二个颜色序列（字符串 B）

输出： 将第一个灯泡链转换为第二个灯泡链所需的最少操作数（整数）

示例输入1：“asdfgh” 输入2：“sdfgh”

输出：1

输入1：“x” 输入2：“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];
}