Leetcode 17 : Letter Combinations of a Phone Number

Question

Problem Statement

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

enter image description here

Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]

My Solution

A simple DFS based approach. Ignore some comments that are for my learning purposes (for similar problems to able to code it fast).

#include <array>
#include <string>
#include <vector>
class Solution {
private:
 // any auxilliary fields to help us (the "fluff" in the problem)
 std::array<std::string_view, 10> mappings = {
 "0", "1", "abc", "def", "ghi", "jkl",
 "mno", "pqrs", "tuv", "wxyz"}; // note that 0 and 1 have the digits since
 // that makes the most sense
 // private functions that (may) do the heavy lifting
 std::string_view getLettersMapping(char digit) {
 return mappings[digit - '0'];
 }
 void dfs(std::vector<std::string> &combinations, std::string_view digits,
 std::string &s, size_t curr_idx, const size_t &N) {
 // base case
 if (curr_idx == N) {
 // last digit's combination has already been explored, so simply append it
 // to our set of combinations and return
 combinations.push_back(s);
 return;
 }
 // determine current mapping digit
 auto letters = getLettersMapping(digits[curr_idx]);
 // for that particular digit, generate all the possible combinations by
 // recursing for each possible digit in the next index.
 for (const auto &ch : letters) {
 // note that passing the string s by reference saves space,
 // but now we need to modify it by adding the letter and then removing the
 // latest added later after the recursive call
 s.push_back(ch);
 dfs(combinations, digits, s, curr_idx + 1, N);
 s.pop_back();
 }
 }
public:
 std::vector<std::string> letterCombinations(std::string digits) {
 // in the main function, we develop the answer, call the "magic"
 // recursion/DFS function, and return the answer
 std::vector<std::string> ans;
 if (digits.empty() || digits.size() == 0) {
 return ans;
 }
 std::string s;
 dfs(ans, digits, s, 0, digits.size());
 return ans;
 }
};

---

Any suggestions for my code? Also, I'm still learning the more "modern" features of C++ (anything from C++17 onwards), so any such advice would be very welcome :)

Answer 1

Make mappings static constexpr

This mapping should never be changed, so ideally it should be constexpr. You also need only one instance of it, so it should be marked static as well (also, constexpr requires this). So:

static constexpr std::array<const std::string_view, 10> mappings = {
 ...
};

This also means getLetterMappings() can be made static constexpr, and in fact you can make dfs() static constexpr as well, although the constexpr part doesn't do much there.

Redundant check for empty input

Why do you check both digits.empty() and digits.size() == 0? Those expressions are equivalent. I would just check for digits.empty().

Unnecessary parameters curr_idx and N

Since you are passing the input digits to dfs() as a std::string_view by value, you don't need the parameters curr_idx and N. Just pass a modified version of digits to recursive calls to dfs(), like so:

void dfs(std::vector<std::string> &combinations, std::string_view digits, std::string &s) {
 if (digits.empty()) {
 combinations.push_back(s);
 return;
 }
 auto letters = getLettersMapping(digits.front());
 for (const auto &ch : letters) {
 s.push_back(ch);
 dfs(combinations, digits.substr(1), s);
 s.pop_back();
 }
}