华为机试079计算字符串相似度

题目描述：

针对各类字符串，我们期望能够找到一种方式来评估其相似性。为此，我们设定了一组操作规则，使得两个不同的字符串可以转化为一致的形式，具体的操作方式如下：

1. 替换某一字符，例如将“a”替换为“b”。

2. 插入一个字符，例如将“abdd”转换为“aebdd”。

3. 删除一个字符，例如将“travelling”转换为“traveling”。

以“abcdefg”和“abcdef”为例，我们可以认为通过添加或删除一个“g”的方式实现两者的统一。上述两种处理方案均只需执行一次操作。我们将完成该操作所需的次数定义为两个字符串之间的距离，并且相似度等于距离加一的倒数。也就是说，“abcdefg”与“abcdef”的距离为1，其相似度则为1/2=0.5。

若给定任意两个字符串，你是否能够设计出一种算法来计算它们的相似度？

Java实现：

 import java.util.Scanner;

    
 public class Main {
    
     public static void main(String[] args) {
    
         Scanner in = new Scanner(System.in);
    
         while(in.hasNext()){
    
             Strin