Clone an ArrayList to another ArrayList does not work in DP

Here is the Java code to find the shortest concatenation of elements of Array wordBank to construct String Terget, using Dynamic Programming.

Example:

Input: wordBank = {“ab”, “c”, “d”, “abc”, “ad”}, Target = “abcd”.

Output: {“abc”, “d”}.

To do this, I have stored the combination of elements as an ArrayList in a HashMap. However, the hashMap does not store the values correctly, i.e., the values change when I recursively call the function, although I have cloned the ArrayList before adding it to the map.

Any idea why this happens?

The code works well with arrays.

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

The problem is the interaction between these lines:

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

and

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

If you return the memoized list, you’re updating it before you clone it.

In general, don’t rely on callers to “do the right thing”: if you don’t want the list in the map to be updated, do the copy yourself before you return it:

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

You may also need to handle the case of a string not being able to be constructed from the word bank.