首页 > 代码库 > 动态规划：编辑距离和通配符匹配
动态规划：编辑距离和通配符匹配
编辑距离指通过修改，删除，添加。使得两个字符串能够相同所需要操作的次数。
edit(i,j) if S1[i]==S2[j] temp=0; else temp=1; edit(i,j)=min(A[i-1][j-1]+temp,A[i-1][j]+1,A[i][j-1]+1); edit(i,j)=min(A[i-1][j-1]+temp,A[i-1][j]+1,A[i][j-1]+1);公式可以理解成，
如果由S1或者增加，删除，替换一次，同两个字符串的推前一个的编辑距离比较。最小值即编辑距离。
1 public static int editDistance(String S1,String S2){ 2 if (S1.equals("")) { 3 return S2.length(); 4 } 5 if (S2.equals("")) { 6 return S1.length(); 7 } 8 int[][] A=new int[S2.length()+1][S1.length()+1]; 9 for(int i=0;i<(S1.length()+1);i++)10 A[0][i]=i;11 for(int i=0;i<(S2.length()+1);i++)12 A[i][0]=i;13 for (int i = 1; i < (S1.length()+1); i++) {//列14 for (int j = 1; j < (S2.length()+1); j++) {15 int temp=1;16 if (S1.substring(i-1, i).equals(S2.substring(j-1, j))) 17 temp=0;18 int a=A[j-1][i]+1;//删除一个19 int b=A[j][i-1]+1;20 int c=A[j-1][i-1]+temp;//替换21 A[j][i] =min(A[j-1][i]+1, A[j][i-1]+1, A[j-1][i-1]+temp);22 }23 }24 return A[S2.length()][S1.length()];25 }
通配符也可以由动态规划计算。
?任意一个字符，*匹配一个或多个任意字符。
如果模式串是?或P[i]==S[j]，则由P[i-1]和S[j-1]是否匹配决定当前是否匹配
如果模式串是*，则由P[i-1],S[j-1];P[i-1],S[j];P[i],S[j-1]决定是否匹配。
比如模式串是"012?4*",匹配字符串是"1234567";则匹配成功
1 public static int min(int a,int b,int c){ 2 return a>b?(b>c?c:b):(a>c?c:a); 3 } 4 public static boolean match(String str,String pattern){ 5 int[][] A=new int[pattern.length()+1][str.length()+1]; 6 A[0][0]=1; 7 char[] strChar=str.toCharArray(); 8 char[] patChar=pattern.toCharArray(); 9 if (patChar[0]==‘*‘) {10 for(int i=0;i<str.length()+1;i++)11 A[0][i]=1;12 }13 for(int i=1;i<pattern.length()+1;i++){14 for (int j = 1; j < str.length()+1; j++) {15 if(patChar[i-1]==‘?‘||(patChar[i-1]==strChar[j-1]))16 A[i][j]=A[i-1][j-1];17 else if (patChar[i-1]==‘*‘&&(A[i-1][j-1]==1||A[i-1][j]==1||A[i][j-1]==1)) 18 A[i][j]=1;19 }20 }21 if(A[pattern.length()][str.length()]==1)22 return true;23 else24 return false;25 }
动态规划：编辑距离和通配符匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。