C BackTrack 3ms


  • 0
    M

    "/**

    • Return an array of size *returnSize.
    • Note: The returned array must be malloced, assume caller calls free().
      */

    void backtrack_LetterCombination_Leetcode_17(char* candidates[],int k,int len,char** returnArray,int* count,char historyChar[]);
    bool is_a_solution_LetterCombination_Leetcode_17(int k,int len);
    void process_solution_LetterCombination_Leetcode_17(int* count);
    void make_move_LetterCombination_Leetcode_17(char c,int k,char** returnArray,int* count,char historyChar[]);
    void unmake_move_LetterCombination_Leetcode_17(char c,int k,char** returnArray,int* count);
    void construct_candidates_LetterCombination_Leetcode_17(char* candidates[],int k,char c[],int* ncandidates);

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

    int count = 0;
    char** returnArray =(char**)malloc(sizeof(char*)*1000);
    char historyChar[4];
    
    char* s[10] = {"","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"," "};
    
    char* candidates[10];
    int i;
    for(i = 0;i < len; ++i){
        candidates[i] = (char*)malloc(sizeof(char)*4);
    }
    for(i = 0;i< 1000; ++i){
        returnArray[i] = (char*)malloc(sizeof(char)*26);
    }
    for(i = 0;i < len; ++i){
        if(digits[i] == '1' || digits[i] == '0'){
            (*returnSize) = 0;
            return NULL;
        }
        else{
            candidates[i] = s[digits[i] - '1'];
        }
    }
    backtrack_LetterCombination_Leetcode_17(candidates,-1,len,returnArray, &count,historyChar);
    (*returnSize) = count;
    return returnArray;
    

    }
    void backtrack_LetterCombination_Leetcode_17(char* candidates[],int k,int len,char** returnArray,int* count,char historyChar[]){
    char c[26] ;
    int ncandidates = 0;
    int i;
    if(is_a_solution_LetterCombination_Leetcode_17(k,len)){
    process_solution_LetterCombination_Leetcode_17(count);
    }
    else{
    ++k;
    construct_candidates_LetterCombination_Leetcode_17(candidates,k,c,&ncandidates);
    for(i = 0;i < ncandidates; ++i){
    make_move_LetterCombination_Leetcode_17(c[i],k,returnArray,count,historyChar);
    backtrack_LetterCombination_Leetcode_17(candidates,k,len,returnArray,count,historyChar);
    unmake_move_LetterCombination_Leetcode_17(c[i],k,returnArray,count);
    }
    }
    }
    bool is_a_solution_LetterCombination_Leetcode_17(int k,int len){
    return k == len-1;
    }
    void process_solution_LetterCombination_Leetcode_17(int* count){
    (*count) ++ ;

    }
    void make_move_LetterCombination_Leetcode_17(char c,int k,char** returnArray,int* count,char historyChar[]){
    int i = k;
    while(i!= 0){
    returnArray[count][i-1] = historyChar[i-1];
    --i;
    }
    returnArray[count][k] = c;
    historyChar[k] = c;
    }
    void unmake_move_LetterCombination_Leetcode_17(char c,int k,char
    returnArray,int* count){
    returnArray[count][k] = '\0';
    }
    void construct_candidates_LetterCombination_Leetcode_17(char
    candidates[],int k,char c[],int* ncandidates){
    int length = strlen(candidates[k]);
    int i;
    for(i = 0;i < length; ++i){
    c[i] = candidates[k][i];
    (*ncandidates)++;
    }
    }

    "


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.