LeetCode 17. Letter Combinations of a Phone Number ( C ) – Medium (遞迴法)

傳統手機透過數字鍵來打字，一個數字鍵通常代表了多個英文字母，例如 2 代表 a , b , c ，3 代表 d , e , f 等，連續按多個鍵能產生英文字母的組合，此題為給定數字，輸出所有可能的英文字母組合。

原文題目如下

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.

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"]
 
Constraints:

0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].
Accepted
 861,326
   Submissions
 1,706,491

解題方式為透過遞迴的方式，透過 for 迴圈把每個數字可能的英文字母遍歷出來，分別遞迴。填完字母後，補上結束字元 ‘ \0 ‘ 轉存回要回傳的空間內。

下面是我的程式碼

char map[10][5]={{},{},{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
int reindex = 0;
char **re;
char *DPtr;
void Rnum( int index, char *tempstr){  // index use for input string index and tempstr index
	if(DPtr[index] == '\0'){
		tempstr[index] = '\0';
		re[reindex] = (char*)malloc(sizeof(char)*(strlen(DPtr)+1));
		strcpy(re[reindex],tempstr);
		reindex++;
	}
	else{
		for(int i = 0;i<strlen(map[DPtr[index]-'0']);i++){
			tempstr[index] = map[DPtr[index]-'0'][i];
			Rnum(index+1,tempstr);
		}
	}
}

char ** letterCombinations(char * digits, int* returnSize){
	DPtr = digits;
    reindex = 0;
	
    if(strlen(digits) != 0){
        (*returnSize) = 1;
        for(int i = 0 ; i < strlen(digits) ; i++ ){
            (*returnSize) *= strlen(map[digits[i]-'0']);
        }
    }
    else{
        (*returnSize) = 0;
    }
	re = (char**)malloc(sizeof(char*)*(*returnSize));
   
	char tempstr[5] = {0};
    if((*returnSize)>0)
	    Rnum( 0, tempstr);

    return re;

}

下面是時間與空間之消耗

Runtime: 0 ms, faster than 100 % of C online submissions for Letter Combinations of a Phone Number.

Memory Usage: 5.7 MB, less than 98.79 % of C online submissions for Letter Combinations of a Phone Number.

下一題連結 : LeetCode 18. 4Sum ( C ) – Medium (雙指標法、搜尋法)