将一个 ArrayList 克隆到另一个 ArrayList 在 DP 中不起作用

Question

这里是 Java 代码，使用动态规划找到数组 wordBank 元素的最短串联以构造字符串 Terget。

示例：

输入： wordBank = {"ab", "c", "d", "abc", "ad"}, 目标 = "abcd".

输出： {"abc", "d"}。

为此，我将元素的组合作为 ArrayList 存储在 HashMap 中。但是，hashMap 没有正确存储值，即当我递归调用该函数时值发生变化，尽管我在将 ArrayList 添加到地图之前克隆了它。

知道为什么会这样吗？

该代码适用于数组。

static ArrayList<String> bestConstruct(String target, String[] wordBank, HashMap<String, ArrayList<String>> map) {
    
    if(target.isEmpty())
    {
        return new ArrayList<String>();
    }
    
    if(map.containsKey(target))
        return map.get(target);
    
    ArrayList<String> shortestCombination = null;
    for (String word : wordBank) {
        
        if(target.startsWith(word)) {
            String newTarget = target.substring(word.length(), target.length());
            
            ArrayList<String> combination = bestConstruct(newTarget, wordBank, map);
            
            
            if(combination != null) {
                combination.add(word);
                
                if(shortestCombination == null || combination.size() < shortestCombination.size())
                    shortestCombination = (ArrayList<String>)(combination.clone());
            }
        }
    }
    map.put(target,  (ArrayList<String>) (shortestCombination.clone()));
    return shortestCombination;
}

Answer 1

问题是这些行之间的交互：

    if(map.containsKey(target))
        return map.get(target);

和

            ArrayList<String> combination = bestConstruct(newTarget, wordBank, map);
            
            
            if(combination != null) {
                combination.add(word);

如果您 return 记忆列表，则在克隆它之前对其进行更新。

一般来说，不要依赖调用者“做正确的事”：如果您不想更新地图中的列表，请在 return 之前自己进行复制：

    if(map.containsKey(target))
        return new ArrayList<>(map.get(target));

您可能还需要处理无法从词库构造字符串的情况。

将一个 ArrayList 克隆到另一个 ArrayList 在 DP 中不起作用

Clone an ArrayList to another ArrayList does not work in DP

java

arraylist

dynamic-programming