最近几天，发现了一个比较好玩的code的网站，相比较熟知的leetcode,我个人更加感兴趣的刷题网站CodeWars,它是一种升级的模式，每次根据所做题目的难度去获取相对应的分值，然后升级，最后还有一个排名榜，感觉挺新颖的，目前属于菜鸟级Level 6,希望努力升到level 3。
在CodeWars上面看到这样一道题目：我们经常使用搜索引擎，有的时候我们打错了字，也能够搜索出我们想要的结果，因为它里面有一个数据库，把你输入的值和数据库中的数据，作比较返回数据库中字符串和你输入字符串最相近的字符串，然后根据这个最相近的字符串进行搜索。
“字符相近的”规则定义: 一个字符经过增，删，替换变成目标字符串，操作数量最小，最相近
解题思路
解题思路：我们操作字符串时，肯定是一个一个字符开始的，每轮到一个字符，总会有四种选择：不操作，删，增，替换，这是比较典型的动态规划的问题，把每一个小的问题解决了，大问题就解决了
我们假设str1的长度为m ,str2的长度为n 定义count[i][j]表示 str1[0,1,2,,,i-1]转换为 str2[0,1,2….j-1]的最少操作数。
动态规划的典型特点是，你在求count[i][j]的时候是要依赖之前已经算好了的值count[i-1][j-1],count[i][j-1],count[i-1][j]这些基础之上的。
假设我们求 count[i][j] 那么可能遇到这几种情况：
- 如果str1[i-1]==str2[j-1] 那么就说明不需要替换
- 如果 str1[i-1]!=str2[j-1] 那么就有多种操作
(1) 替换操作 count[i][j]=count[i-1][j-1]+1
(2) 删除操作 count[i][j]=count[i-1][j]+1 //删除这个数字才能，使得0-i和0-j 相等，说明要让0-i-1 和0-j相等才行
(3) 增加操作 count[i][j]=count[i][j-1] //增加遇到的元素，使得0-i和0-j相等，要求0-i和0-j-1相等就行
然后比较这三个数字的最小值，就是理想操作了
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static int minstance(String str1,String str2){
if(str1==null && str2==null)
return 0;
int n1;
int n2;
if(str1==null)
n1=0;
else
n1=str1.length();
if(str2==null)
n2=0;
else
n2=str2.length();
int[][] dp=new int[n1+1][n2+1];
for(int i=0;i<=n1;i++)
dp[i][0]=i; //如果str2为空
for(int j=0;j<=n2;j++)
dp[0][j]=j; //如果str1为空
for(int i=1;i<=n1;i++)
for(int j=1;j<=n2;j++){
if(str1.charAt(i-1)==str2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1];
}
else
dp[i][j]=1+Math.min(dp[i-1][j-1],Math.min(dp[i-1][j], dp[i][j-1]));
}
return dp[n1][n2];
}
又到了一年的高考，高考真的算是人生中比较印象深刻的经历。
