Leetcode - 17. Letter Combinations of a Phone Number

9405 ワード
leetcode Backtracking HashTable テキストリンク

質問する


次の携帯電話のキーボードに、与えられた数字がどの文字の組み合わせになるかを出力します.(与えられた数字の桁数が4以下)
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

解決する


問題を追跡する.まず、各キーボード数字をキーとし、使用可能な文字列を値とするハッシュテーブルを作成します.可能なすべての組合せ文字を遡及的に作成します.次のtmp配列を予め作成して再帰的に呼び出すと、現在のテーブル文字を現在のidxに保存し、次の再帰関数に送信します.
動的にchar **resultが割り当てられ、最後の基本的な状況でstrcpy tmpが割り当てられる.二重ポインタのみが割り当てられているため、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;
}
[アルゴリズム解析]プログラマーゲームマップ最短距離
スレッドが中断する