aboutsummaryrefslogtreecommitdiff
path: root/letter_tile_possibilities.c
diff options
context:
space:
mode:
Diffstat (limited to 'letter_tile_possibilities.c')
-rw-r--r--letter_tile_possibilities.c35
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
+}