动态规划：编辑距离和通配符匹配

编辑距离指通过修改，删除，添加。使得两个字符串能够相同所需要操作的次数。

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         else
24             return false;
25     }