/**
 * 給出字符串：str1渴肉、str2忽匈；判斷這兩個(gè)字符串的相似度有多大；
 * 編輯距離：可通過增刪改，將str1操作某一或某幾個(gè)字符轉(zhuǎn)換成str2，其中改變最小的距離，為最優(yōu)。
 * Dp規(guī)劃實(shí)現(xiàn)編輯距離的相似度測算
 * 空間復(fù)雜度：O(mn)
 * 時(shí)間復(fù)雜度：O(mn)
 * @author Administrator
 */
public class EditDistanceUtils {

    /**
     * Dp規(guī)劃實(shí)現(xiàn)的編輯距離
     * 步驟：
     * 1、構(gòu)建一個(gè)二維數(shù)組嘁信；
     * 2于样、初始化input、target中每個(gè)字符的索引位置潘靖，分別初始化值的位置是第一行與第一列穿剖，表示input與target；
     * 3卦溢、根據(jù)判斷糊余，算出對應(yīng)二維數(shù)組坐標(biāo)處對應(yīng)的編輯距離；（這里的距離单寂，就是距離目標(biāo)的字符的索引數(shù)值差）
     * 4贬芥、最后的對角值即為最終編輯距離的結(jié)果
     * **/
    private static int getEditDistance(String input, String target){
        try {
            int m = input.length();
            int n = target.length();
            if(m <= 0){
                return n;
            }
            if(n <= 0){
                return m;
            }
            //構(gòu)建二維數(shù)組，并初始化
            int[][] matrix = new int[m][n];
            for(int i = 0; i < m; ++i){
                matrix[i][0] = i;
            }
            for(int i = 0; i < n; ++i){
                matrix[0][i] = i;
            }
            //遍歷整個(gè)二維數(shù)組宣决，獲取每個(gè)字符所在位置的編輯距離蘸劈；因?yàn)橐?jì)算i-1、j-1的位置尊沸，故從i/j=1開始
            for(int i = 1; i < m; ++i){
                for(int j = 1; j < n; ++j){
                    int c = input.charAt(i) == target.charAt(j) ? 0 : 1;
                    //i-1威沫、j-1是算上一個(gè)交叉點(diǎn)的位置坐標(biāo)；i-1洼专、j與i棒掠、j-1為相鄰兩側(cè)，從索引處已經(jīng)減1屁商，故加1
                    matrix[i][j] = Math.min(matrix[i-1][j-1] + c, Math.min(matrix[i -1][j] + 1, matrix[i][j - 1] + 1));
                }
            }

            return matrix[m - 1][n - 1];
        }catch (Exception e){
            e.printStackTrace();
        }
        return 0;
    }

    /**
     * 計(jì)算兩個(gè)字符串的 相似度
     * **/
    public static Double getSimilarity(String input, String target){
        Integer distance = getEditDistance(input, target);

        Double similarity = 1 -  distance.doubleValue() / Math.max(input.length(), target.length());
        return similarity;
    }

    /**
     * 計(jì)算輸入字符串烟很，與其他多個(gè)字符串的相似度
     * **/
    public static Map<String, Double> getSimilarityMap(String input, String... targets){
        try{
            if(input.length() <= 0){
                return Collections.EMPTY_MAP;
            }
            if(targets == null || targets.length <= 0){
                return Collections.EMPTY_MAP;
            }
            LinkedHashMap<String,Double> linkedHashMap = new LinkedHashMap<>();
            String target = "";
            for(int i = 0; i < targets.length; ++i){
                target = targets[i];
                Double similarity = getSimilarity(input, target);
                linkedHashMap.put(target, similarity);
            }
            return linkedHashMap;
        }catch (Exception e){
            e.printStackTrace();
        }
        return Collections.EMPTY_MAP;
    }

    /**
     * 計(jì)算輸入字符串，與其他多個(gè)字符串的相似度
     * **/
    public static Map<String, Double> getSimilarityMap(String input, Double limit, String... targets){
        try{
            Map<String, Double> linkedHashMap = getSimilarityMap(input, targets);
            List<String> keyList =  linkedHashMap.keySet().stream().collect(Collectors.toList());
            LinkedHashMap<String, Double> limitMap = new LinkedHashMap<>();
            String key = "";
            Double value = 0D;
            for(int i = 0; i < keyList.size(); ++i){
                key = keyList.get(i);
                value = linkedHashMap.getOrDefault(key, 0D);
                if(value >= limit){
                    limitMap.put(key, value);
                }
            }
            return limitMap;
        }catch (Exception e){
            e.printStackTrace();
        }
        return Collections.EMPTY_MAP;
    }

    public static void main(String[] args) {

        getSimilarityMap("haizeiwang", 0.8D,"haizhughaiwang","haizaiwang","haizaiwatg");
    }

}