17. Phone numbers

#include <stdlib.h>
#include <string.h>

static const char *mapping[10] = {"",    "",    "abc",  "def", "ghi",
                                  "jkl", "mno", "pqrs", "tuv", "wxyz"};

static void backtrack(const char *digits, int n, int idx, char *cur,
                      char **result, int *returnSize) {
  if (idx == n) {
    result[(*returnSize)++] = strdup(cur);
    return;
  }
  for (const char *ch = mapping[digits[idx] - '0']; *ch; ch++) {
    cur[idx] = *ch; // choose
    backtrack(digits, n, idx + 1, cur, result, returnSize);
  } // un-choose is implicit: cur[idx] is overwritten next time
}

char **letterCombinations(char *digits, int *returnSize) {
  *returnSize = 0;
  int n = strlen(digits);
  if (n == 0)
    return NULL;

  int total = 1;
  for (int i = 0; i < n; i++)
    total *= strlen(mapping[digits[i] - '0']);

  char **result = malloc(total * sizeof(char *));
  char *cur = calloc(n + 1, 1);
  backtrack(digits, n, 0, cur, result, returnSize);
  free(cur);
  return result;
}

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
  vector<string> letterCombinations(string digits) {
    vector<string> result;
    if (digits.empty())
      return result;
    string cur;
    backtrack(digits, 0, cur, result);
    return result;
  }

private:
  const vector<string> mapping = {"",    "",    "abc",  "def", "ghi",
                                  "jkl", "mno", "pqrs", "tuv", "wxyz"};

  void backtrack(const string &digits, int idx, string &cur,
                 vector<string> &result) {
    if (idx == (int)digits.size()) {
      result.push_back(cur);
      return;
    }
    for (char ch : mapping[digits[idx] - '0']) {
      cur.push_back(ch); // choose
      backtrack(digits, idx + 1, cur, result);
      cur.pop_back(); // un-choose
    }
  }
};

package backtracking

var mapping = [10]string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}

func letterCombinations(digits string) []string {
    var result []string
    if len(digits) == 0 {
        return result
    }
    cur := make([]byte, 0, len(digits))

    var backtrack func(idx int)
    backtrack = func(idx int) {
        if idx == len(digits) {
            result = append(result, string(cur))
            return
        }
        for _, ch := range []byte(mapping[digits[idx]-'0']) {
            cur = append(cur, ch) // choose
            backtrack(idx + 1)
            cur = cur[:len(cur)-1] // un-choose
        }
    }

    backtrack(0)
    return result
}

import java.util.ArrayList;
import java.util.List;

class Solution {
    private static final String[] MAPPING = {"", "", "abc", "def", "ghi",
                                             "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.isEmpty()) {
            return result;
        }
        backtrack(digits, 0, new StringBuilder(), result);
        return result;
    }

    private void backtrack(String digits, int idx, StringBuilder cur, List<String> result) {
        if (idx == digits.length()) {
            result.add(cur.toString());
            return;
        }
        for (char ch : MAPPING[digits.charAt(idx) - '0'].toCharArray()) {
            cur.append(ch); // choose
            backtrack(digits, idx + 1, cur, result);
            cur.deleteCharAt(cur.length() - 1); // un-choose
        }
    }
}

const MAPPING = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  const result = [];
  if (digits.length === 0) return result;
  const cur = [];

  const backtrack = (idx) => {
    if (idx === digits.length) {
      result.push(cur.join(""));
      return;
    }
    for (const ch of MAPPING[digits[idx]]) {
      cur.push(ch); // choose
      backtrack(idx + 1);
      cur.pop(); // un-choose
    }
  };

  backtrack(0);
  return result;
};

from typing import List

MAPPING = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        result: List[str] = []
        if not digits:
            return result
        cur: List[str] = []

        def backtrack(idx: int) -> None:
            if idx == len(digits):
                result.append("".join(cur))
                return
            for ch in MAPPING[int(digits[idx])]:
                cur.append(ch)  # choose
                backtrack(idx + 1)
                cur.pop()  # un-choose

        backtrack(0)
        return result

const MAPPING: [&str; 10] = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];

impl Solution {
    pub fn letter_combinations(digits: String) -> Vec<String> {
        let mut result = Vec::new();
        if digits.is_empty() {
            return result;
        }
        let mut cur = String::with_capacity(digits.len());
        Self::backtrack(digits.as_bytes(), 0, &mut cur, &mut result);
        result
    }

    fn backtrack(digits: &[u8], idx: usize, cur: &mut String, result: &mut Vec<String>) {
        if idx == digits.len() {
            result.push(cur.clone());
            return;
        }
        for ch in MAPPING[(digits[idx] - b'0') as usize].chars() {
            cur.push(ch); // choose
            Self::backtrack(digits, idx + 1, cur, result);
            cur.pop(); // un-choose
        }
    }
}