shunfurh 于 2017.08.29 20:30 提问

DICS

Problem Description
I think all of you must be skilled in the classic problem Levenshtein Distance , which is more commonly known as Edit Distance. For more historic knowledge and basic concepts, see http://en.wikipedia.org/wiki/Levenshtein_distance .
This time, we are involved in a more complicated one: given two strings SOURCE and DESTINATION , we have 4 operations
Delete: remove the ith character.
Insert: in pos i(the ith character in the first string),you can insert a character, any one as you like.
Change: in pos i,you can change that original character to any other character(of course you won't change it to itself).
Suffix change: which means you can change all characters to an identical character, from the ith pos to the end. For instance: abcdefg, you can make this operation in character b,maybe you can use d and the result is adddddd, or if you use e the result is aeeeeee or if you use this operation in character c with character f,the result is abfffff.
With the help of Suffix change, sometimes the edit distance can be greatly shortened. See the following example

abcdefg
ccccccg

You can first replace every character from the beginning to the end with c,and the first string will be ccccccc,then change the last character c to g. In such way,we can see the edit distance is 2.

Input
Input consists of several test cases, each case contains two line,the first line will show you the SOURCE string, the second line provide the DESTINATION string. You should write a program to caculate the minimum number of operations(delete, insert, changes, suffix change as I mentioned before) of transforming the SOURCE to DESTINATION. You can assume none of string in any case will be longer than "500". Input ends with a line consists of a '#'.
PAY ATTENTION:Both strings consist of either lower or upper letters,in other word in each position there is 52 possibilities.There will be at most 15 test cases.

Output
One line for each case,the edit distance. Output nothing for the "#".

Sample Input
abcdefg
aaaaaaa
#

Sample Output
1

1个回答

caozhy      2017.09.13 23:52

dictPython内置了字典：dict的支持，dict全称dictionary，在其他语言中也称为map，使用键-值（key-value）存储，具有极快的查找速度。 举个例子，假设要根据同学的名字查找对应的成绩，如果用list实现，需要两个list： names = [‘Michael’, ‘Bob’, ‘Tracy’] scores = [95, 75, 85] 给定一个名字，要查找对应
HDU 3831 DICS

HDU 3831 DICS 递推dp

learn python the hard way---ex50,ex51
windows 以下代码不一定能运行，直接建文件即可\$ cd projects \$ mkdir gothonweb \$ cd gothonweb \$ mkdir bin gothonweb tests docs templates \$ touch gothonweb/__init__.py \$ touch tests/__init__.py
python3 字典遍历操作
python字典遍历
discuz论坛用户密码加密原理

iOS NSPredicate数组筛选
NSPredicate条件查询NSPredicate的作用 简述：Cocoa框架中的NSPredicate用于查询，原理和用法都类似于SQL中的where，作用相当于数据库的过滤取。 **条件查询一般是运用于按照条件要求将数组中符合条件的数据筛选出来形成一个新的数组，主要的功能大概如下：代码，例如：NSMutableArray *preditArray = [NSMutableArray arr