字母組合 - 通過功能

Question

問題

給出一個數字串傳遞一個數組，返回所有可能的字母組合，該數字可能代表。 （輸出：數字字符串「23」，輸出：[「ad」，「ae」，「af」，「bd」，「be」，「bf」，「cd」，「 CE」， 「CF」]

問題

我感到困惑，從LeetCode下面的解決方案代碼。爲什麼傳遞result數組通過遞歸調用result數組在letterCombinations？是否因爲結果數組在遞歸調用getString引用了相同的結果數組？

public List<String> letterCombinations(String digits) { 
    HashMap<Integer, String> map = new HashMap<>(); 
    map.put(2, "abc"); 
    map.put(3, "def"); 
    map.put(4, "ghi"); 
    map.put(5, "jkl"); 
    map.put(6, "mno"); 
    map.put(7, "pqrs"); 
    map.put(8, "tuv"); 
    map.put(9, "wxyz"); 
    map.put(0, ""); 

    ArrayList<String> result = new ArrayList<>(); 

    if (digits == null || digits.length() == 0) { 
     return result; 
    } 

    ArrayList<Character> temp = new ArrayList<>(); 
    getString(digits, temp, result, map); 

    return result; 
} 

public void getString(String digits, ArrayList<Character> temp, ArrayList<String> result, 
     HashMap<Integer, String> map) { 
    if (digits.length() == 0) { 
     char[] arr = new char[temp.size()]; 
     for (int i = 0; i < temp.size(); i++) { 
      arr[i] = temp.get(i); 
     } 
     result.add(String.valueOf(arr)); 
     return; 
    } 

    Integer curr = Integer.valueOf(digits.substring(0, 1)); 
    String letters = map.get(curr); 
    for (int i = 0; i < letters.length(); i++) { 
     temp.add(letters.charAt(i)); 
     getString(digits.substring(1), temp, result, map); 
     temp.remove(temp.size() - 1); 
    } 
} 

Answer 1

是因爲在以往的遞歸調用getString結果數組引用相同的結果數組？

答案是是。

爲什麼通過遞歸調用傳遞result數組會改變letterCombinations中的result數組？

數組的傳遞result在letterCombinations中改變了數組並且getString調用引用了相同的結果數組。由於它是一個遞歸方法調用，它在每次迭代之後都會上傳並將值存儲到同一個引用。這是主要原因，爲什麼每次迭代或遞歸調用都有不同的值。因此它也會影響實際的數組。

Answer 2

首先，我會指出，儘管您從中獲得該網站的名稱，但這不是特別明確的代碼。

對getString()的呼叫有三個變化參數 - digits，temp和result。

map永不改變 - 如果它是一個常數，它會更好，更清晰。假設它是，那麼getString()的簽名是getString(String digits, List<Character> temp。

命名不明顯，但temp包含「到目前爲止完成的工作」，所以我們第一次稱它爲空列表。

讓我們看看會發生什麼它第一次被調用，以digits == 234和temp空單：

• digits.length() != 0 - 所以我們跳過整個第一塊。
• 我們搶到第一位，2並查找其文字在地圖 - 通過信件"a"
• 我們循環：
  • 我們把'a'到的temp末，使temp == ['a']
  • 那麼我們調用getString("34", ['a'])
  • 我們從temp刪除最後一個項目，使得temp == []
  • 那麼同樣的與'b' - getString("34",['b'])
  • 那麼同樣用'c' - getString("34",['c'])

然後我們就大功告成了。但是那些遞歸調用發生了什麼？

按照邏輯getString("34",['a'])，你會看到它如何從digits獲得3，並撥打電話getString("4", ['a','d'])。

反過來getString("4", ['a','d'])撥打電話，如getString("",['a','d','g'])。

最後我們處於遞歸停止的位置。看看當我們調用getString("",['a','d','g'])會發生什麼：

• digits.length == 0，所以我們進入if塊，並返回 - 我們不進步入將再次調用getString()的組成部分。
• 我們（以一種費力的方式）將temp中的字符加入String，並將其添加到result。
• 就是這樣。

更好的代碼：

if(digits.isEmpty()) { 
    result.add(String.join("",temp)); 
    return; 
} 

我們從來沒有創建了一個新result - 我們只是傳遞了相同的一個（同一map太）至getString()每次調用。所以當一個getString()添加一個項目時，當下一個getString()添加一個項目時，該項目仍然存在。

---

遞歸方法通常可以理解爲：

def recursivemethod(params) { 
     if(it's a no-brainer) { 
      output an answer 
     } else { 
      do a little bit of the job 
      call recursiveMethod(newParams) 
     } 
} 

在這種情況下，這是一個沒有腦子的時候digits是空的 - 整個的答案是temp，只是需要增加結果列表。

如果這不是一件容易的事情，那麼「工作的一小部分」就是處理第一位數字，並對它可能代表的每個可能的字母進行遞歸。

---

清潔在我看來

，在保持原有的精神：

private static final Map<Character, String> DECODINGS = new HashMap<>(); 
static { 
    DECODINGS.put('2', "abc"); 
    // <snip> 
} 

public List<String> letterCombinations(String digits) { 
    ArrayList<String> result = new ArrayList<>(); 
    addCombinationsToList(digits, "", result); 
    return result; 
} 

private void addCombinationsToList(String digits, String prefix, List<String> list) { 
    if (digits.isEmpty()) { 
     list.add(prefix); 
    } else { 
     String letters = DECODINGS.get(digits.charAt(0)); 
     for (int i = 0; i < letters.length(); i++) { 
      addCombinationsToList(digits.substring(1), prefix + letters.charAt(i), list); 
     } 
    } 
} 

通過建立一個不變的字符串prefix + letters.charAt(i)而不是操縱可變List<Character>，您就不必把它放回你的方式找到它，使代碼更容易理解。