Блог

Вот код Java для поиска кратчайшего объединения элементов массива wordBank для построения строки Terget с использованием динамического программирования.

Пример:

Ввод: Банк слов = {«ab», «c», «d», «abc», «ad»}, Цель = «abcd».

Вывод: {«abc», «d»}.

Для этого я сохранил комбинацию элементов в виде списка массивов в хэш-карте. Однако хэш-карта не хранит значения правильно, т. Е. Значения меняются, когда я рекурсивно вызываю функцию, хотя я клонировал список массивов перед добавлением его на карту.

Есть идеи, почему это происходит?

Код хорошо работает с массивами.

 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;
}
 

Проблема заключается во взаимодействии между этими линиями:

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

и

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

Если вы возвращаете список с памятью, вы обновляете его, прежде чем клонировать.

В общем, не полагайтесь на то, что звонящие «поступят правильно»: если вы не хотите, чтобы список на карте обновлялся, сделайте копию самостоятельно, прежде чем возвращать его:

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

Возможно, вам также потребуется обработать случай, когда строка не может быть создана из банка слов.