/**//*问题描述：设S1和S2是两个字符串。要用最少的字符操作将字符串S1转换为字符串S2。这里的字符串操作包括：
(1)删除一个字符
(2)插入一个字符
(3)将一个字符改成为另一个字符。
将字符串S1转换为字符串S2的所用的最少的字符串操作数称作字符串S1到S2的最短距离，记为 d(S1, S2).
算法设计：给定字符串S1和S2，计算它们的最短编辑距离d(S1, S2)。
*/
/**//*算法思想：
用数组b[i][j]记录s1[1..i]和s2[1..j]之间的编辑长度。
递归公式
b[i][j]=min(b[i-1]][j],b[i][j-1],b[i][j]+(s1[i]==s2[i]?0:1));
*/
public class EditDistance
{
public int editDistance(String s,String aim)
{
int sLength=s.length()+1;
int aLength=aim.length()+1;
int[][] b=new int[aLength][sLength];
for(int i=1;i<sLength;i++)
{
b[0][i]=i;
}
for(int k=1;k<aLength;k++)
{
b[k][0]=k;
}
for(int j=1;j<sLength;j++)
{
for(int i=1;i<aLength;i++)
{
int x=b[i-1][j]+1;
int y=b[i][j-1]+1;
int z=b[i-1][j-1]+((s.charAt(i-1)==aim.charAt(j-1))?0:1);
b[i][j]=min(x,y,z);
}
}
return b[aLength-1][sLength-1];
}
public int min(int x,int y,int z)
{
int temp;
if(x<y)
{
temp=x;
}
else temp=y;
if(z<temp) temp=z;
return temp;
}
public static void main(String []args)
{
String s="hhdeihhh";
System.out.println(s.length());
String aim="hheepppk";
System.out.println(aim.length());
EditDistance ed=new EditDistance();
System.out.println(ed.editDistance(s,aim));
}
}posted on 2008-06-26 10:53
夏日清风 阅读(693)
评论(0) 编辑 收藏 所属分类:
算法