动态规划实现最短字符串拼接时ArrayList克隆失效问题咨询

• 缓存读取无拷贝：Java中集合为引用传递，你存入HashMap时虽然做了克隆，但命中缓存调用map.get(target)时，直接返回了缓存中ArrayList对象的引用。后续代码拿到该引用后直接执行combination.add(word)，相当于直接修改了HashMap中存储的缓存列表，自然会出现异常变更。
• 空指针隐患：如果当前target无法被wordBank中的元素拼接，shortestCombination会为null，此时执行shortestCombination.clone()会直接抛出空指针异常。

修改核心逻辑为：读取缓存时返回克隆值，修改递归返回的组合前先做拷贝，避免修改原缓存对象。修复后的代码如下：

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 (ArrayList<String>) map.get(target).clone();
    }
    ArrayList<String> shortestCombination = null;
    for (String word : wordBank) {
        if(target.startsWith(word)) {
            String newTarget = target.substring(word.length());
            ArrayList<String> combination = bestConstruct(newTarget, wordBank, map);
            if(combination != null) {
                // 先克隆再修改，不要修改递归返回的原对象
                ArrayList<String> newCombination = (ArrayList<String>) combination.clone();
                newCombination.add(word);
                if(shortestCombination == null || newCombination.size() < shortestCombination.size()) {
                    shortestCombination = newCombination;
                }
            }
        }
    }
    // 空值判断，避免空指针
    if(shortestCombination != null) {
        map.put(target, (ArrayList<String>) shortestCombination.clone());
    } else {
        map.put(target, null);
    }
    return shortestCombination;
}

内容的提问来源于stack exchange，提问作者Elahe