# SPOJ 6219. Edit Distance (EDIST) with F#

 (* * Problem URI : http://www.spoj.com/problems/EDIST/ * Problem Code : EDIST * Date : 27.01.2013 *) (* * Algorithmic Technique * ======================= * _Dynamic Programming_ with Memoization is applied to solve this problem (i.e. to * compute _edit distance). First we derive a recursive definition of Edit Distance and * afterwards, solve the subproblems. * * Lets denote ``distance'' to be the function that calculates edit distance. * The recursive definition can be stated as follows: * * Base cases: * -------------- * distance ("","") --> 0 * distance ("",s2) --> |s2| * distance (s1,"") --> |s1| * * * distance (s1+ch1, s2+ch2) --> * min{ distance(s1+ch1, s2) + 1, //cost: insertion of ch2 in s1+ch1 * distance(s1, s2+ch2) + 1, //cost: deletion of ch1 from s1 * distance(s1,s2) + (if ch1=ch2 then 0 else 1) // cost of substitution * } *) open System let min ((a:int), (b:int), (c:int)) = Math.Min(a, Math.Min(b,c)) let computeEditDistance (source:string,target:string) = let height,width = (source.Length, target.Length) let grid: int [,] = Array2D.zeroCreate (height+1) (width+1) for h = 0 to height do for w = 0 to width do grid.[h,w] <- match h,w with | h,0 -> h | 0, w -> w | h, w -> let s,t = source.[h-1],target.[w-1] let insertion = grid.[h,w-1] + 1 let deletion = grid.[h-1,w] + 1 let substitution = grid.[h-1,w-1]+(if s = t then 0 else 1) min (insertion, deletion, substitution) grid.[height,width] //Trivial IO Stuff let parseLine() = let word1 = System.Console.ReadLine() let word2 = System.Console.ReadLine() word1,word2 let solveEdist() = let T = System.Console.ReadLine() // Total Number of cases //printfn "string cases : %s" s let numCases = System.Int32.Parse(T) //printfn "cases : %d" numCases for j = 1 to numCases do parseLine() |> computeEditDistance |> printfn "%d" solveEdist()
view raw edist.fs hosted with ❤ by GitHub