読者です 読者をやめる 読者になる 読者になる

日々精進

新しく学んだことを書き留めていきます

SRM497 Div2 Hard

IT TopCoder

http://www.topcoder.com/stat?c=problem_statement&pm=8681&rd=14426
問題の分析
与えられた文字列を「真ん中から前半・後半に分けたときに前半と後半が同じとなる文字列」に編集する場合の最小編集距離を求めなさい。
方針
任意の二つの文字列の最小編集距離はDPで求められる。
GREE伊藤直也さんの記事にDPの解説がありました。これを読めば最小編集距離の出し方はわかると思います。http://d.hatena.ne.jp/naoya/20090329/1238307757
与えられた文字列を0〜n-1の場所で区切り、前半と後半に分ける。前半を後半と同じ文字列に編集するときの最小編集距離をすべての場所で区切った場合について求め、その最小値を返す。

ソースコード

using System;
using System.Collections.Generic;
using System.Text;
 
 
public class MakeSquare
{
    public int minChanges(String S)
    {
        int min = int.MaxValue;
        for (int i = 0; i < S.Length; i++)
        {
            string first = S.Substring(0, i);
            string second = S.Substring(i, S.Length - i);
            min = Math.Min(EditDistance(first, second), min);
        }
        return min;
    }
 
 
    private int EditDistance(string from, string to)
    {
        int[,] dp = new int[from.Length + 1, to.Length + 1];
        for (int i = 0; i < from.Length + 1; i++)
            dp[i, 0] = i;
        for (int i = 0; i < to.Length + 1; i++)
            dp[0, i] = i;
        for (int i = 1; i < from.Length + 1; i++)
        {
            for (int j = 1; j < to.Length + 1; j++)
            {
                int x;
                if (from[i - 1].Equals(to[j - 1]))
                    x = 0;
                else
                    x = 1;
                dp[i, j] = Math.Min(Math.Min(dp[i - 1, j] + 1, dp[i, j - 1] + 1), dp[i - 1, j - 1] + x);
            }
        }
        return dp[from.Length, to.Length];
    }
}