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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (* * 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