Leetcode - 17. Letter Combinations of a Phone Number

문제

주어진 숫자가 아래 휴대폰 키패드에서 어떤 문자의 조합이 될 수 있는지 출력하기. (주어진 숫자 자릿수는 0이상 4이하)

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

해결

Backtracking 문제. 우선 각 키패드 숫자를 key로 하고 사용가능한 문자열을 value로 하는 해시 table생성 하고. 백트래킹 방식으로 모든 가능성의 조합문자를 만들어냄. 아래 tmp 배열을 미리 생성하고 재귀적으로 호출할때 현재 idx에 현재 테이블 문자를 저장하고 다음 재귀함수에 보냄.
char **result 를 동적 할당하고, 마지막 base case에서 tmp를 strcpy함. 더블포인터만 할당했기 때문에 그 안의 char * 타입 값도 미리 동적할당 해야함.

Backtracking 참고할만한 영상 : https://www.youtube.com/watch?v=Ar40zcPoKEI

char table[8][5] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
int reslen;

int hash(char c)
{
    return c - '2';
}

void back_tracking(char *d, int idx, int dsize, char **res, char *tmp)
{
    /* Base Case */
    if (idx >= dsize) {
        if (!dsize) return;
        //printf("%s ", tmp);
        res[reslen] = (char *)malloc(strlen(tmp) + 1);
        strcpy(res[reslen++], tmp);
        return;
    }
    /* Recursion */
    char *c = table[hash(d[idx])]; 
    for (int i = 0; i < strlen(c); i ++) {
        tmp[idx] = c[i];
        back_tracking(d, idx + 1, dsize, res, tmp);
    }
}

char ** letterCombinations(char * digits, int* returnSize){
    char **result = (char **)malloc(sizeof(char *) * 4000);
    char tmp[6] = {0,};
    reslen = 0;
    back_tracking(digits, 0, strlen(digits), result, tmp);
    *returnSize = reslen;
    return result;
}

221021 다시 풀어봄

class Solution {
    string map[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> ret;
    
    void backtracking(string s, string combi, int pos) {
        if (pos > s.length())
            return;
        if (pos == s.length()) {
            if (pos != 0)
                ret.push_back(combi);
            return;
        }
            
        string btn = map[s[pos] - '0'];
        for (int i = 0; i < btn.length(); i++) {
            backtracking(s, combi + btn[i], pos + 1);
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        string combi = "";
        backtracking(digits, combi, 0);
        return ret;
    }
};