Leetcode

LeetCode 17.電話番号の文字の組み合わせ（Java）



Leetcode 17 Letter Combinations Phone Number



トピック：

2〜9の数字を含む文字列を指定すると、その数字が表す可能性のあるすべての文字の組み合わせを返します。

数字から文字へのマッピング（電話ボタンの場合と同様）を以下に示します。 1はどの文字にもマップされないことに注意してください。
画像



例：
入力：「23」
出力：[「ad」、「ae」、「af」、「bd」、「be」、「bf」、「cd」、「ce」、「cf」]。

注意：
上記の回答は辞書式順序ですが、回答は任意の順序にすることができます。



回答：

解決策1：HashMap +複数のループ

この質問は私が暴力的な解決策を考えただけでした。
つまり、すべての数字に対応する文字がループを介して順番に取り出され、ネストされたトラバーサルが実行されます。 HashMapを使用して、数字と文字の間のKey-Value関係を格納します。

ループネスティングのアイデアは次のとおりです：

  1. ループの最初のレベル：ループdigits.length（）、順番に入力された各桁を取り出し、HashMapのget（）メソッドを使用して対応する文字値substrを取り出します
  2. 次に、次の番号に対応する値を取り出し、ネストされたループを実行して、順列と組み合わせを実現します。
    たとえば、最初の数字2はabcに対応します。このとき、リスト配列の値は[a、b、c]であり、次の番号3がループされます。これは、リスト内のdef、traverse Valuesに対応し、それぞれa、b、cとd、eのスペルです。 、f、順番にループし、最後にリストに戻ります
class Solution { public List<String> letterCombinations(String digits) { Map<Character, 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') List<String> list = new ArrayList<>() if(digits.length()==0) { return list } list.add('') for(int i=0 i<digits.length() i++) { List<String> temp = new ArrayList<>() String substr = map.get(digits.charAt(i)) for(String str: list) { for(int j=0 j<substr.length() j++) { String strsum = str + substr.charAt(j) temp.add(strsum) } } list = temp } return list } }

画像



解決策2：キュー+ループ

または、キューの先入れ先出しの性質を水平方向の組み合わせに使用できます
考え：

  1. 最初に入力の最初の数字を取り出し、それが表す文字列を見つけ、文字をトラバースして順番にキューに入れます
  2. 次に、入力された次の番号を取り出し、それが表す文字列を見つけ、順番にキューから取り出し、現在の文字列で表されている各文字と順番に組み合わせて、もう一度キューに入ります。
  3. キュー内のすべての文字列の長さ==入力文字列の長さの場合、すべての組み合わせが完了します。したがって、キューの先頭にある要素の長さは、res.peek（）。length（）を使用して取得し、それがdigits.length（）と同じであるかどうかを判別できます。
    （したがって、2番目のステップでは、キュー内の文字長で入力された次の番号を取得できます）
class Solution { public List<String> letterCombinations(String digits) { LinkedList<String> res = new LinkedList<>() String[] map = new String[] {'','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz'} if(digits.length()==0) { return res } res.add('') while(res.peek().length() != digits.length()) { String temp = res.pop() String str = map[digits.charAt(temp.length()) - '0'] for(char c: str.toCharArray()) { res.add(temp + c) } } return res } }

このメソッドのコードはより簡潔ですが、ソリューションのコードと同じ考え方であるため、時間計算量も同じです。
画像

解決策3：バックトラック

「バックトラッキング」アルゴリズム ：これは、列挙に似た検索試行プロセスであり、主に検索試行プロセス中に問題の解決策を見つけることです。解の条件が満たされていないことが判明すると、「バックトラック」して別のパスを試行します。バックトラッキング法は一種の最適な検索方法であり、目標を達成するために最適な条件に従って前方に検索します。しかし、彼が特定のステップを調査したとき、彼は元の選択が良くないか、目標を達成しなかったことに気づいたので、彼は一歩下がって別の選択をしました。
ほとんどのバックトラッキングの問題は、再帰、深さ優先、完全な順列など、いくつかの要素から切り離せません。

質問を分析すると、質問の出力近似は、条件を満たすすべての順列の列挙であることがわかります。つまり、1つの位置を修正し、毎回他の位置を変更します
入力した数字が「234」の場合、最初の文字には「a」、「b」、「c」の3つの選択肢があります。最初の文字がaの場合、2番目の文字には3つの選択肢があり、2番目の文字を選択した後、3番目の文字には3つの選択肢があります...など、この論理的な考え方は非常に似ていることがわかります。ツリー構造に、すべてがレイヤーで増加します。 、各レイヤーのノードは複数の子ノードに対応します。
したがって、「バックトラッキング」のアイデアで解決できます。

class Solution { private static final String[] map = new String[] {'','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz'} public List<String> letterCombinations(String digits) { List<String> res = new ArrayList<>() if(digits.length()==0) { return res } doCombination(new StringBuffer(), res, digits) return res } private void doCombination(StringBuffer str, List<String> res, String digits) { //str reaches the expected length, that is, after completing a combination, save str into res if(str.length() == digits.length()) { res.add(str.toString()) return } //Read the optional character set corresponding to the element traversed by the current digits String substr = map[digits.charAt(str.length())-'0'] //Traverse the optional character set, fix the character at the current position each time, and then select the next character for(char c: substr.toCharArray()) { str.append(c) //Add to doCombination(str, res, digits) // recursion str.deleteCharAt(str.length() - 1) //delete } } }

画像