DPL_1_E: Edit Distance (Levenshtein Distance)

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

// Q079 レーベンシュタイン距離 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_E&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("acac");
            WillReturn.Add("acm");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("icpc");
            WillReturn.Add("icpc");
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        string S1 = InputList[0];
        int UB_X = S1.Length;

        string S2 = InputList[1];
        int UB_Y = S2.Length;

        int[,] DPArr = new int[UB_X + 1, UB_Y + 1];

        // 初期値の設定
        for (int X = 0; X <= UB_X; X++) {
            DPArr[X, 0] = X;
        }
        for (int Y = 0; Y <= UB_Y; Y++) {
            DPArr[0, Y] = Y;
        }

        // 貰うDPで解く
        for (int X = 1; X <= UB_X; X++) {
            for (int Y = 1; Y <= UB_Y; Y++) {
                char CurrStr1 = S1[X - 1];
                char CurrStr2 = S2[Y - 1];

                var KouhoList = new List<int>();

                // 候補1 上のマスの値+1
                KouhoList.Add(DPArr[X, Y - 1] + 1);

                // 候補2 左のマスの値+1
                KouhoList.Add(DPArr[X - 1, Y] + 1);

                // 候補3の1 左上のマスの値+1
                if (CurrStr1 != CurrStr2) {
                    KouhoList.Add(DPArr[X - 1, Y - 1] + 1);
                }
                else { // 候補3の2 左上のマスの値
                    KouhoList.Add(DPArr[X - 1, Y - 1]);
                }

                DPArr[X, Y] = KouhoList.Min();
            }
        }
        Console.WriteLine(DPArr[UB_X, UB_Y]);
    }
}

解説

下記のマトリックス表で
「すうがく」の0文字目から4文字目までのそれぞれの文字列
「すがた」の0文字目から3文字目までのそれぞれの文字列
のレーベンシュタイン距離を考えます。

　□すうがく
□？？？？？
す？？？？？
が？？？？？
た？？？？？

空文字との編集距離は、自明なので埋めます。

　□すうがく
□０１２３４
す１？？？？
が２？？？？
た３？？？？

以下は、下記の3通りの候補の最小値を埋めるロジックで
レーベンシュタイン距離が求まります。

候補1 上のマスの値+1
候補2 左のマスの値+1
候補3の1 左上のマスの値+1 (文字が一致しない場合)
候補3の2 左上のマスの値 (文字が一致する場合)

　□すうがく
□０１２３４
す１０１２３
が２１１１２
た３２２２２