diff options
Diffstat (limited to 'letter_tile_possibilities.c')
-rw-r--r-- | letter_tile_possibilities.c | 35 |
1 files changed, 35 insertions, 0 deletions
diff --git a/letter_tile_possibilities.c b/letter_tile_possibilities.c new file mode 100644 index 0000000..3b9268c --- /dev/null +++ b/letter_tile_possibilities.c @@ -0,0 +1,35 @@ +// 1079. Letter Tile Possibilities +#include "leetcode.h" + +/* + * given 'n' tiles where each tile has one letter ('tiles[i]') printed on it. + * return the number of possible non-empty letters printed on those tiles. + */ + +void dfs(int *alpha, int *sum) { + for (int i = 0; i < 26; i++) { + if (!alpha[i]) + continue; + (*sum)++; + alpha[i]--; + dfs(alpha, sum); + alpha[i]++; + } +} + +int numTilePossibilities(char *tiles) { + int *alpha = calloc(26, sizeof(int)); + for (int i = 0; i < strlen(tiles); i++) + alpha[tiles[i] - 'A']++; + int ans = 0; + dfs(alpha, &ans); + free(alpha); + return ans; +} + +int main() { + char *t1 = "AAB", *t2 = "AAABBC", *t3 = "V"; + printf("%d\n", numTilePossibilities(t1)); // expect: 8 + printf("%d\n", numTilePossibilities(t2)); // expect: 188 + printf("%d\n", numTilePossibilities(t3)); // expect: 1 +} |