1

这里可以避免递归吗？这里的 Java 代码处理两个字符串。找到可以将一个字符串转换为另一个字符串的最少方法。一次我们可以从字符串中删除字符、添加字符或替换字符。

公共类MinimumWays {

public static int colorSequences(String input1,String input2)
{


    return new MinimumWays().transform(input1, input2);
}

public int transform(String inp1, String inp2){
    int a  = 0; int b=0; int c=0; int result =0;
    if(inp1.length()==0){
        result = inp2.length();
        return result;
    }
    else if(inp2.length()==0){
        result =inp1.length();
        return result;
    }
    if(inp1.substring(0, inp1.length()-1).equals(inp2)||inp1.substring(1, inp1.length()).equals(inp2)){
         a=0;
         return a;
    }
    else{
        a = Math.min(transform(inp1.substring(0, inp1.length()-1), inp2), transform(inp1.substring(1, inp1.length()), inp2) );
    }
    if(inp2.substring(0, inp2.length()-1).equals(inp1)||inp2.substring(1,inp2.length()).equals(inp1)){
         b=0;
         return b;
    }
    else{
        b = Math.min(transform(inp2.substring(0, inp2.length()-1), inp1),transform(inp2.substring(1,inp2.length()), inp1));
    }
    if(inp2.substring(0, inp2.length()-1).equals(inp1.substring(0, inp1.length()-1))|| 
            inp2.substring(0, inp2.length()-1).equals(inp1.substring(1, inp1.length())) || 
              inp2.substring(1, inp2.length()).equals(inp1.substring(0, inp1.length()-1)) ||
                inp2.substring(1, inp2.length()).equals(inp1.substring(1, inp1.length()))){
         c=0;
         return c;
    }
    else{
        int c1 = transform(inp2.substring(0, inp2.length()-1), inp1.substring(0, inp1.length()-1));
        int c2 = transform(inp2.substring(1, inp2.length()), inp1.substring(0, inp1.length()-1));
        int c3 = transform(inp2.substring(0, inp2.length()-1), inp1.substring(1, inp1.length()));
        int c4 = transform(inp2.substring(1, inp2.length()), inp1.substring(1, inp1.length()));
        c = Math.min(Math.min(c1, c2), Math.min(c3, c4));
    }

    result = 1+Math.min(a, Math.min(c, b));
    return result;
}



public static void main(String[] args) {
    String input1 = "sakdh";
    String input2 = "akh";
    System.out.println("Minimum Ways: " + colorSequences(input1, input2));

}

}

虽然功能上很好，但对于大字符串（即使是 6-7 个字符），它需要很多时间。我无法找出任何其他编码方式。:-(

4

2 回答 2

2

这就是编辑距离，一个常见的二维动态规划问题。您可以使用递归和记忆或迭代解决。

试试这个：

HashMap<List<String>, Integer> memo = new HashMap<List<String>, Integer>();

public int transform(String inp1, String inp2){
{
    List<String> temp = new ArrayList<String>();
    temp.add(inp1);
    temp.add(inp2);
    if (memo.containsKey(temp))
    {
        return memo.get(temp);
    }
    ...

其他人会打败我，但请确保在返回之前将答案存储到 HashMap 中。如果它们已经被计算，这将使对函数的调用立即返回，而不是重新计算。

于 2013-10-28T21:08:10.347 回答
0

这被称为“编辑距离”问题。有一种更有效的方法可以解决这个问题。对于动态规划，这个问题是 O(MN)，其中 M 和 N 是每个字符串中的字符数。这是有关该主题的一些材料...

http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Lec6-EditDistance.pdf

于 2013-10-28T21:04:45.480 回答