//

// 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 */