1 
    private static int editDistance(ArrayList<String> s1, ArrayList<String> s2) {
        if (s1.size()==0) {
            return s2.size();
        } 
        else if (s2.size()==0) {
            return s1.size();
        } 
        else {
            String temp1 = s1.remove(s1.size()-1);
            String temp2 = s2.remove(s2.size()-1);
            if (temp1.equals(temp2)) {
                return editDistance((ArrayList<String>)s1.clone(),(ArrayList<String>)s2.clone());
            } else {
                s1.add(temp1);
                int first = editDistance((ArrayList<String>)s1.clone(),(ArrayList<String>)s2.clone())+1;
                s2.add(temp2);
                s1.remove(s1.size()-1);
                int second = editDistance((ArrayList<String>)s1.clone(),(ArrayList<String>)s2.clone())+1;
                s2.remove(s2.size()-1);
                int third = editDistance((ArrayList<String>)s1.clone(),(ArrayList<String>)s2.clone())+1;
                if (first <= second && first <= third ) {
                    return first;
                } else if (second <= first && second <= third) {
                    return second;
                } else {
                    return third;
                }
            }
        }
    }

例如，输入可以是["div","table","tr","td","a"]and ["table","tr","td","a","strong"]，对应的输出应该是2。

我的问题是当任一输入列表的大小太大时，例如，列表中有 40 个字符串时，程序会产生can't reserve enough space for object heap错误。JVM 参数是-Xms512m -Xmx512m. 我的代码可能需要这么多堆空间吗？还是由于我的代码中的逻辑错误？

编辑：无论是否克隆列表，这种递归方法似乎都不起作用。有人可以帮助估计为我工作所需的总堆内存吗？我想这会令人震惊。无论如何，我想我必须改用动态编程方法。

4

1 回答 1

2

您在每次递归调用您的方法之前的clone()每个实例。ArrayList这实质上意味着您将获得整个列表的另一个副本及其每次调用的内容 - 它可以轻松地添加到非常大的内存量以实现大递归深度。

您应该考虑使用List#sublist()而不是clone()，甚至向您的方法添加参数以将索引传递给一组初始List对象。

于 2012-12-10T12:04:55.187 回答