字母组合 - 通过功能

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>，您就不必把它放回你的方式找到它，使代码更容易理解。