Letter Phone

• Time : $O(|s|^3)$
• Space : $O(|s|)$

unordered_map<char,string> mp {{'1',"1"}, {'2',"abc"}, {'3',"def"},
 {'4',"ghi"},{'5',"jkl"},{'6',"mno"},
 {'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"},
 {'0',"0"}};

void helper(vector<string>& res, string& A, int p, string& now) {
    if(p == A.size()) res.push_back(now);
    else {
        for(auto ch : mp[A[p]]) {
            now.push_back(ch);
            helper(res,A,p+1,now);
            now.pop_back();
        }
    }
}
vector<string> Solution::letterCombinations(string A) {
    vector<string> res;
    helper(res, A, 0, string() = "");
    return res;
}