算法題之字符串相似度

問題描述

面試阿里的時候問了我一個問題，如何求兩個字符串之間的相似度，當(dāng)時不知道該怎么回答，后來下來之后從網(wǎng)上查看才知道這是一個經(jīng)典的動態(tài)規(guī)劃題。
兩個字符出的相似度定義為：將一個字符串轉(zhuǎn)換成另一個字符串的代價（通過插入、刪除、替換三種方式轉(zhuǎn)換），轉(zhuǎn)換的代價越高則說明兩個字符串的相似度越低。

問題分析

這是一個典型的動態(tài)規(guī)劃題。我們知道，可以用動態(tài)規(guī)劃求解的題都有最優(yōu)子結(jié)構(gòu)性質(zhì)，回到這個問題當(dāng)中，假設(shè)source有字符串有n個字符，target字符串有m個字符，如果將問題定義為求解將source的1到n個字符轉(zhuǎn)換為target的1到m個字符所需要的最少編輯次數(shù)（最小編輯距離），則子問題就可以定義為將source的1到i個字符轉(zhuǎn)換為target的1到j(luò)個字符所需要的最少編輯次數(shù)，這就是本問題的最優(yōu)子結(jié)構(gòu)。我們用d[i,j]表示source[1...i]到target[1...j]之間的最小編輯距離，則計算d[i,j]的遞推關(guān)系可以這樣計算出來
當(dāng)source[i]==target[j]時
d[i,j] = d[i-1,j-1]+0
如果source[i]!=target[j]，則根據(jù)插入、刪除和替換三個策略，分別計算出使用三種策略得到的編輯距離，然后取最小的一個：
d[i,j]=min(d[i-1][j]+1,d[i][j-1]+1,d[i-1,j-1]+1)
其中：
d[i][j-1]+1表示對source[i]執(zhí)行插入操作后計算編輯最小距離
d[i-1][j]+1表示對source[i]執(zhí)行刪除操作后計算最小編輯距離
d[i-1,j-1]+1表示對source[i]替換成target[i]操作后計算最小編輯距離

代碼實現(xiàn)

import java.util.Scanner;

public class StringSimilar {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String source = scan.nextLine();
        String target = scan.nextLine();
        System.out.println(editDistance(source,target));
        
    }
    public static int editDistance(String source,String target){
        char[] sources = source.toCharArray();
        char[] targets = target.toCharArray();
        int m = source.length();
        int n = target.length();
        int[][] distance = new int[m+1][n+1];
        int i,j;
        for(i=0;i<=m;i++){
            distance[i][0]=i;
        }
        for(j=0;j<=n;j++){
            distance[0][j]=j;
        }
        for(i=1;i<=m;i++){
            for(j=1;j<=n;j++){
                if(sources[i-1]==targets[j-1]){
                    distance[i][j]=distance[i-1][j-1];
                }else{
                    int insert = distance[i][j-1]+1;
                    int delete = distance[i-1][j]+1;
                    int replace =distance[i-1][j-1]+1;
                    distance[i][j]= Math.min(insert, delete)>replace?replace:Math.min(insert, delete);
                }
                
            }
        }
        
        return distance[m][n];
    }
}