Letter Combinations of a Phone Number

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        const vector<string> M = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        vector<string> out;
        string path;
        function<void(int)> dfs = [&](int i){
            if (i == (int)digits.size()) { out.push_back(path); return; }
            for (char c : M[digits[i] - '0']) {
                path.push_back(c);
                dfs(i + 1);
                path.pop_back();
            }
        };
        dfs(0);
        return out;
    }
};

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }
    m := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
    out := []string{}
    path := []byte{}
    var dfs func(i int)
    dfs = func(i int) {
        if i == len(digits) {
            out = append(out, string(path))
            return
        }
        for j := 0; j < len(m[digits[i]-'0']); j++ {
            path = append(path, m[digits[i]-'0'][j])
            dfs(i + 1)
            path = path[:len(path)-1]
        }
    }
    dfs(0)
    return out
}

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        m = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        out: List[str] = []
        path: List[str] = []

        def dfs(i: int) -> None:
            if i == len(digits):
                out.append(''.join(path))
                return
            for c in m[int(digits[i])]:
                path.append(c)
                dfs(i + 1)
                path.pop()

        dfs(0)
        return out

function letterCombinations(digits) {
    if (digits.length === 0) return [];
    const m = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    const out = [];
    const path = [];
    const dfs = (i) => {
        if (i === digits.length) {
            out.push(path.join(''));
            return;
        }
        for (const c of m[Number(digits[i])]) {
            path.push(c);
            dfs(i + 1);
            path.pop();
        }
    };
    dfs(0);
    return out;
}

class Solution {
    private static final String[] M = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    private String digits;
    private List<String> out;
    private StringBuilder path;

    public List<String> letterCombinations(String digits) {
        out = new ArrayList<>();
        if (digits.isEmpty()) return out;
        this.digits = digits;
        path = new StringBuilder();
        dfs(0);
        return out;
    }

    private void dfs(int i) {
        if (i == digits.length()) {
            out.add(path.toString());
            return;
        }
        String letters = M[digits.charAt(i) - '0'];
        for (int j = 0; j < letters.length(); j++) {
            path.append(letters.charAt(j));
            dfs(i + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

function letterCombinations(digits: string): string[] {
    if (digits.length === 0) return [];
    const m: string[] = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    const out: string[] = [];
    const path: string[] = [];
    const dfs = (i: number): void => {
        if (i === digits.length) {
            out.push(path.join(''));
            return;
        }
        for (const c of m[Number(digits[i])]) {
            path.push(c);
            dfs(i + 1);
            path.pop();
        }
    };
    dfs(0);
    return out;
}