-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution17.hpp
More file actions
58 lines (51 loc) · 1.99 KB
/
Solution17.hpp
File metadata and controls
58 lines (51 loc) · 1.99 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//
// Solution17.hpp
// Algorithm
//
// Created by Pancf on 2019/12/3.
// Copyright © 2019 Pancf. All rights reserved.
//
#ifndef Solution17_hpp
#define Solution17_hpp
#include <iostream>
#include <string>
#include <vector>
using std::string;
using std::vector;
class Solution17 {
/**
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
（参照九宫格键盘）
Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
================================================================================================
Accept details:
*BFS*
Runtime: 4 ms, faster than 60.33% of C++ online submissions for Letter Combinations of a Phone Number.
Memory Usage: 8.5 MB, less than 88.57% of C++ online submissions for Letter Combinations of a Phone Number.
*DFS*
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Letter Combinations of a Phone Number.
Memory Usage: 8.4 MB, less than 100.00% of C++ online submissions for Letter Combinations of a Phone Number.
思路：这道题有两种方法，一种类似于DFS，一种类似于BFS。
把输入的数字字符串每个数字当作结点，每个数字有3-4片叶子，以数字2为例
2
/ | \
a b c
后续的数字作为前一个数字每片叶子的叶子，以此类推会得到一棵树。两种方法其实就是遍历这颗树的两种方法了。
*/
public:
vector<string> letterCombinations(string digits);
static void test() {
Solution17 s = Solution17();
string param = "234";
vector<string> str_vector = s.letterCombinations(param);
for (auto s : str_vector) {
std::cout<<s<<std::endl;
}
}
};
#endif /* Solution17_hpp */