# Leetcode 17 Solution

https://leetcode.com/problems/letter-combinations-of-a-phone-number

## Thinking Process

Finding all the combinations means we’ll have to iterate all the cases without missing a single one. We typically do that with a DFS recursion.

Whenever we try to design a DFS algorithm, always do the following two things:

• define the states
• define the state transition tree

The state of the algorithm can be represented by `(i, curr)`, where `i` is current index of `digit`, and `curr` means the current string formed.

• Apparently, if `i == len(digit)`, we reached to an end, we can append `curr` to the final result.
• Otherwise, find out the matching characters, and for each of them, append it to `curr` str, and iterate for the index `i + 1`.

## Time & Space Complexity

Assuming `N` is the length of digit

• Time complexity: `O(2^N)`
• Space complexity: `O(N)`

## Solution

``````class Solution {
vector<string> m_res;
vector<string> m_chars;

public:
void letterCombinations(const string& digits, int i, string& curr) {
if (i == digits.size())
{
if (curr.size() != 0)
m_res.push_back(curr);
return;
}

int digit = digits[i] - '0';

for (const char& ch : m_chars[digit])
{
curr += ch;
letterCombinations(digits, i + 1, curr);
curr = curr.substr(0, curr.size() - 1);
}
}

vector<string> letterCombinations(string digits) {
m_chars.push_back("");
m_chars.push_back("");
m_chars.push_back("abc");
m_chars.push_back("def");
m_chars.push_back("ghi");
m_chars.push_back("jkl");
m_chars.push_back("mno");
m_chars.push_back("pqrs");
m_chars.push_back("tuv");
m_chars.push_back("wxyz");

string curr;

letterCombinations(digits, 0, curr);
return m_res;
}
};
``````