概述
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
思路
动态规划
代码
package com.lilei.spring_boot_db.boot.pack1115;
public class edit_distance {
public static void main(String[] args) {
System.out.println(min_distance("asdfvvvvsds","assdfvvvvsdsds"));
}
static int min_distance(String src, String dest) {
if (src.length() >0 && dest.length() >0) {
char c1 = src.charAt(src.length() - 1);
char c2 = dest.charAt(dest.length() - 1);
int dest_delete = min_distance(src,
dest.substring(0, dest.length() - 1)) + 1;
int src_delete = min_distance(src.substring(0, src.length() - 1),
dest) + 1;
int both_delete = -1;
if (c1 == c2) {
both_delete = min_distance(src.substring(0, src.length() - 1),
dest.substring(0, dest.length() - 1));
} else {
both_delete = min_distance(src.substring(0, src.length() - 1),
dest.substring(0, dest.length() - 1)) + 2;
}
return Math.min(dest_delete, Math.min(src_delete, both_delete));
}else{
if (src.length() == 0){
return dest.length();
}else{
return src.length();
}
}
}
}