字符串比较问题
问题分析：解答此题需要一个较为巧妙的解题思路。解决此题可以借用“最长公共子串”问题的解题思路。采用自底向上的动态规划思想。假设对于给定的字符串A，B长度分别为m,n，A[1..m],B[1..n],这里可以使用变量val[m][n]表示A,B的扩展距离。
对于字符串A[1..m],B[1..n],有以下两种情况：
1.A[m]和B[n]处在扩展字符串的同一个位置，那么val[m][n]=val[m-1][n-1]+abs(A[m]-B[n])。
2.A[m]和B[n]不在扩展字符串的同一个位置，则val[m][n]=min{val[m-1][n]+k,val[m][n-1]+k}。
综上，val[m][n]=min{val[m-1][n]+k，val[m][n-1]+k，val[m-1][n-1]+abs(A[m]-B[n])}
由上述递推式，采用自底向上的方法在多项式时间内即可求出val[m][n](String comparison problem)