典型問題(上級) B 編集距離

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("5 6");
            WillReturn.Add("abcde");
            WillReturn.Add("bcdefg");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

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

        string S2 = InputList[2];
        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]);
    }
}

解説

貰うDPで解いてます。

類題

DPL_1_E: Edit Distance (Levenshtein Distance)