求一个算法：一个字符串变成另一个字符串的编辑过程

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 3456 天前的主题，其中的信息可能已经有所发展或是发生改变。

我在寻找这个算法的过程中找到了 edit distance算法，不过跟我需要的东西不是太一样。
具体的要求就是，给出两个字符串（当然这两个字符串都不会太长，而且一般都会有一定的相似性，当然也有可能完全不相似）

比如：
原始字符串：this is a strings.
目标字符串：This is not a damn string.

算法要求能够整理说从原始字符串到目标字符串所需要的编辑过程。
比如说：
1. 删掉原句开头小写的t
2. 在开头插入大写的T
3. 在某某位置处插入not
4. 在某某位置插入damn
5. 删掉某某位置的字母s

求大神帮忙！！！当然最好是JAVA写的。
多谢！

字符串

插入

原始

15 条回复 • 2015-06-07 20:54:38 +08:00

Kilerd

2015-06-07 09:45:43 +08:00

- this is a strings.
+ This is not a damn string.

Git 的做法 ←_←

hellogbk

2015-06-07 09:48:21 +08:00

@Kilerd 呃好吧，我需要的是一个详细的编辑过程呀。。。

Hyperion

2015-06-07 09:55:54 +08:00

从收藏夹里翻出了这个：
http://article.yeeyan.org/view/67953/33055

Kilerd

2015-06-07 09:57:03 +08:00

@hellogbk 详细算法，就是伸手党了。。。。。

msg7086

2015-06-07 10:03:00 +08:00

https://leetcode.com/problems/edit-distance/

其实就是Edit Distance，只不过原题是以字母为单位，而你这是可以把字母合并成词为单位。

pimin

2015-06-07 10:04:00 +08:00

1.原句拆分,str1="this is a strings.";str2="This is not a damn string.";
拆分成单词词组,words1={"this","is","a","strings"}
1.首字母强制大写转换,
2.找到合适的位置插入你想要插入的单词,比如判断在is,are,之类be动词前后做处理.如果没有怎么处理.
3.重新拼接