LeetCode: Finding all possible letter combinations from an inputted phone number
Preface:

Next time you post code, please include the #includes.  It is easier to review if reviewers can simply copy the code and compile it.  In the same vein, it's helpful if you include any special compiler flags and a test case.  Here is the code as I am reviewing it: https://godbolt.org/z/zQ5mH3.

Review:


You don't write std:: before STL classes so I assume you are using namespace std;.  Many have written about why this is a bad idea so I won't repeat it here, but note it's especially bad in headers (.h files).  It's a less bad in implementations (.cpp files).  You haven't split out your code into a header/implementation, so anyone who #includes your code will also be forced to use namespace std... which is not good.
You use a map&lt;char, vector&lt;char&gt;&gt; to find possible letters from digits.  I think this is OK in cold code/as a mockup implementation while you figure out the rest of your code.  But this is a waste of time/memory in hot code because:


the map is known at compile time
there is no reason to allocate/deallocate anything, and map/vector can both use the heap



Using a function that returns initializer_list&lt;char&gt; instead of a map to vectors speeds up your function 1.6 times (http://quick-bench.com/eYwFgmzQmT95dOsLSRH35FT4QAI).  In case you don't already know, initializer_list is a lightweight data-structure that can be iterated but will not allocate/deallocate memory.  Note that in order to safely return initializer_list, you need to make the list static and might as well make it constexpr.


Your Solution class passes a lot of state in each recursive call.  This call happens many times, so you should try to make it cheap.  For starters you could pass the constant strings by const&amp; to avoid unnecessary copies (this is a 1.9x speed up from the original).  But you could also opt to make the string, result, and digits member variables and then only pass the index in the recursive calls.  This has a few advantages:


Your recursive calls will only have a this pointer and an index (so the arguments will fit in almost every cache line).
It becomes natural to use the same strings the whole time and only copy when producing the result as opposed to the way it was originally written with s + string({c}) which does a heap allocation (at least with std::string and GCC 10).



The simpler recursive calls + the functional map results in a 3.3x speedup compared to the original implementation.  The recursive function now looks like:

void letter_combination_helper(int i) {
  if (i == m_digits.size()) {
    m_result.push_back(m_string);
    return;
  }

  for (char c : lettermap(m_digits[i])) {
    m_string.push_back(c);
    letter_combination_helper(i + 1);
    m_string.pop_back();
  }
}


... where I have prefixed the member variables with "m_" for clarity, and lettermap is a function returning initializer_list&lt;char&gt;.


Minor nit: It's nice to use camelCase or snake_case but not both.
Minor nit 2: I think the indentation of the code you posted is weird e.g. construct_num_letter_map's open bracket is indented but the closing bracket isn't.  This weirdness might have been introduced when you pasted your code into the question, so I won't expand on this.


I think if you make these changes you will have some fast and elegant code.  The general algorithm is the same -- I think you got that right from the start which is good.  I believe the algorithm is optimal since you need O(pow(len(digits), 4)) space to store the result vector, and it seems reasonable to spend that much time writing the answer down.

If I had to summarize the comments into one morsel of feedback, it would be to think more carefully about which operations need to use memory (i.e. allocate/deallocate/copy/dereference).  This was the issue with map (it has to dereference a lot to do lookups) and also with passing lots of state in the recursive calls (lots of copying).  The general rule of thumb is that memory is slow, and if you can reasonably avoid it, then you should.  If you keep at it, this will become second nature to you.