編程之美3.3的一道題，兩字符串相似度定義為兩字符串距離+1的倒數，而字符串距離又被定義為將一個字符串通過（1添加一個字符2刪除一個字符3修改一個字符）這三種基本操作的步數。這樣計算相似度其實就是計算距離，計算字符串距離實際上是經典的DP問題。
現在定義distance[i][j]含義為字符串a[0...i-1]和字符串b[0...j-1]的相似度，則可以知道：
1、distance[0][j] = j;distance[i][0] = i;
2、若a[i - 1] = b[j - 1]則distance[i][j] = distance[i - 1][j - 1];
3、若a[i - 1] != b[j - 1]則distance[i][j]= min(distance[i - 1][j - 1], distance[i - 1][j], distance[i][j - 1]) + 1;
第三種情況可以理解為，如果a字符串的第x個字符不等于b字符串的第y個字符，則可以：1）去掉a字符串的第x個字符，然后再將a[0...x-1]與b[0...y]比較；2）將a字符串的第x個字符修改為b的第y個字符，然后比較a[0...x-1]與b[0...y-1]；3）在a的字符串的第x個字符后面添加b的第y個字符，然后再將a[0...x]與b[0...y-1]比較；或者像以上三步一樣操作b字符串；
這樣得到如下程序：
1 #define min(a, b) ((a) > (b) ? (b) : (a))
2
3 int calculate_string_distance(char *str_a, char *str_b) {
4 int i, j;
5 int str_a_len = strlen(str_a);
6 int str_b_len = strlen(str_b);
7 //gcc允許這么做
8 //但ansi c是不允許這么做的
9 //最好還是用new或者全局數組
10 int distance[str_a_len + 1][str_b_len + 1];
11 for (i = 0; i <= str_a_len; ++i) {
12 distance[i][0] = i;
13 }
14 for (j = 0; j <= str_b_len; ++j) {
15 distance[0][j] = j;
16 }
17 for (i = 1; i <= str_a_len; ++i) {
18 for (j = 1; j <= str_b_len; ++j) {
19 distance[i][j] = distance[i - 1][j - 1];
20 if (str_a[i - 1] != str_b[j - 1]) {
21 distance[i][j] = min(distance[i][j],
22 distance[i - 1][j]);
23 distance[i][j] = min(distance[i][j],
24 distance[i][j - 1]);
25 distance[i][j]++;
26 }
27 }
28 }
29 return distance[str_a_len][str_b_len];
30 }
上面算法是非遞歸程序，如果要寫遞歸代碼，則相對簡單，此處略，不過遞歸代碼由于需要重復計算很多中情況，所以會非常慢。
posted on 2012-09-03 20:52
myjfm 閱讀(708)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎