手紙組み合わせ - 関数を使って配列を渡す

Question

問題

桁の文字列を考えるには、数は表すことができ、すべての可能な文字の組み合わせを返します。入力：数字列 "23"、出力：["ad"、 "ae"、 "af"、 "bd"、 "be"、 "bf"、 "cd"、 " CE」、 "CF"]

質問

私はLeetCodeから以下のソリューションコードについて混乱しています。再帰呼び出しによってresult配列を渡すとresult配列がletterCombinationsに変更されるのはなぜですか？これは、結果の配列が今まで再帰的にgetString呼び出しで同じ結果配列を参照しているためですか？これまで再帰呼び出し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

ですか？

答えははいです。

なぜ再帰呼び出しによってresult配列を渡すと、resultの配列がletterCombinationsに変更されるのですか？

letterCombinationsの配列resultの通過は、配列を変更しgetStringコールは、同じ結果の配列を参照しています。これは再帰的メソッド呼び出しであるため、各反復後にupadを取得し、その値を同じ参照に格納します。これが主な理由です。それぞれの反復または再帰呼び出しごとに異なる値を持つのはなぜですか。したがって、実際の配列にも影響します。

Answer 2

まず、私はあなたがそれを得たサイトの名前にもかかわらず、これは特に明確なコードではないことを指摘します。

getString()への呼び出しには、digits,tempおよびresultの3つの変更パラメータがあります。

mapこれは決して変更されません。定数であれば、より明確になります。ふりをしてみましょう。したがって、getString()の署名はgetString(String digits, List<Character> tempです。

名前は明白ではありませんが、tempには「これまでの作業が含まれています」という内容が含まれているため、初めて呼び出すときは空のリストです。

• digits.length() != 0 - 私たちは、最初のブロック全体をスキップ：

  はのはdigits == 234とtemp空のリストと、それが初めて呼び出されたときに何が起こるのかを見てみましょう。

• 我々は、最初の数字をつかむ2し、マップ内の文字を検索 - 手紙を通して私たちループ"a"
• ：私たちは、その後temp == ['a']
• を作り、tempの終わりに私たちを'a'を入れ
  • その後、同じ我々はtemp == []
  • を作り、tempから最後の項目を削除getString("34", ['a'])
  • を呼び出しますその後、我々が行っているgetString("34",['c'])

から'b'と - 'c'とgetString("34",['b'])

同じ。しかし、再帰呼び出しではどうなりましたか？

getString("34",['a'])のロジックに従うと、3がローカルdigitsからどのようにつかまり、getString("4", ['a','d'])のようにコールされるのがわかります。

getString("4", ['a','d'])はgetString("",['a','d','g'])のようにコールします。

最後に、再帰が停止するレベルにあります。

• digits.length == 0ので、私たちはifブロックに行くと返す - 我々は再びgetString()を呼ぶだろう部分に進まないでください：私たちはgetString("",['a','d','g'])を呼び出すときに何が起こるかを見てください。
• tempからStringに文字を結合し、resultに追加します（面倒な方法で）。
• それだけです。

より良いコード：

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

我々は新しいresultを作成したことがない - 私達はちょうどgetString()のすべての呼び出しに同じもの（とあまりにも同じmap）を渡しています。したがって、1つのアイテムが追加されたときには、次のgetString()に2番目のアイテムが追加されたときにそのアイテムがそのまま残ります。再帰的な方法は、通常のように読み取ることができ

---

：

この場合

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>を操作することによって、あなたは道にあなたをそれを戻すことを避けますそれを見つけて、理解しやすいコードを作りました。