当前位置：网站首页>[record of question brushing] 17 Letter combination of telephone number

[record of question brushing] 17 Letter combination of telephone number

2022-07-22 12:27:00 【InfoQ】

One 、 Title Description

source ：

Power button （LeetCode）

Given a number only  2-9  String , Returns all the letter combinations it can represent . You can press In any order return .

The mapping of numbers to letters is given as follows （ Same as phone key ）. Be careful 1 Does not correspond to any letter .

Example 1：

 Input ：digits = &quot;23&quot;
 Output ：[&quot;ad&quot;,&quot;ae&quot;,&quot;af&quot;,&quot;bd&quot;,&quot;be&quot;,&quot;bf&quot;,&quot;cd&quot;,&quot;ce&quot;,&quot;cf&quot;]

Example 2：

 Input ：digits = &quot;&quot;
 Output ：[]

Example 3：

 Input ：digits = &quot;2&quot;
 Output ：[&quot;a&quot;,&quot;b&quot;,&quot;c&quot;]

Tips ：

0 <= digits.length <= 4

digits[i] Is the scope of ['2', '9'] A number of .

Two 、 Thought analysis

hashMap + DFS Depth-first search

As can be seen from the title , Each number corresponds to a character array . We can use it
map
To save the corresponding relationship

In fact, every number can be regarded as a node of a tree , And the corresponding character , It can be regarded as a branch under this node

Every extra number , It is equivalent to one more corresponding branch under the node of the branch .

Then we traverse the tree to get the final result we want, such as the example above 1：

Code implementation

class Solution1 {
 Map<Character, String> map = new HashMap<Character, String>() {{
 put('2', &quot;abc&quot;);
 put('3', &quot;def&quot;);
 put('4', &quot;ghi&quot;);
 put('5', &quot;jkl&quot;);
 put('6', &quot;mno&quot;);
 put('7', &quot;pqrs&quot;);
 put('8', &quot;tuv&quot;);
 put('9', &quot;wxyz&quot;);
 }};

 public List<String> letterCombinations(String ds) {
 int length = ds.length();

 List<String> res = new ArrayList<>();
 if (length == 0) return res;

 StringBuilder sb = new StringBuilder();
 dfs(ds, 0, length, sb, res);
 return res;
 }

 void dfs(String ds, int i, int n, StringBuilder sb, List<String> res) {
 if (i == n) {
 res.add(sb.toString());
 return;
 }

 char key = ds.charAt(i);

 String letters = map.get(key);
 for (int j = 0; j < letters.length(); j++){
 sb.append(letters.charAt(j));
 dfs(ds, i +1 , n, sb, res);
 sb.deleteCharAt(sb.length() -1);
 }
 }
}