Rosalind第47题：Edit Distance

Problem

Given two strings  and  (of possibly different lengths), the edit distance  is the minimum number of edit operations needed to transform  into , where an edit operation is defined as the substitution, insertion, or deletion of a single symbol.

The latter two operations incorporate the case in which a contiguous interval is inserted into or deleted from a string; such an interval is called a gap. For the purposes of this problem, the insertion or deletion of a gap of length  still counts as  distinct edit operations.

Given: Two protein strings  and  in FASTA format (each of length at most 1000 aa).

Return: The edit distance .

给定两个串 和（可能不同的长度），则编辑距离 是的最小数目的编辑操作转换所需要成，其中的编辑操作被定义为置换，插入，或单个符号的删除。 

后两个操作合并了在字符串中插入或删除连续间隔的情况；这样的间隔称为间隙。出于此问题的目的，插入或删除一定长度的间隙仍然算作不同的编辑操作。

给出：两个蛋白质串， 并采用FASTA格式（每个长度最大为1000aa）。

返回：编辑距离

Sample Dataset

>Rosalind_39
PLEASANTLY
>Rosalind_11
MEANLY

Sample Output

5