1079: Letter-Tile-Possibilities
Medium
table of contents
This week seems to be the week of the backtracking.
A simple recursion algorithm would suffice; just
create an array of size 26 to hold the count of
each letter of the alphabet, and iterate through all possibilities at
each index.
code
class Solution {
public:
int recursion(int index, int length, int *a) {
if (index == length) return 0;
int ans = 0;
for (int i = 0; i < 26; ++i) {
if (a[i] == 0) continue;
--a[i];
++ans;
ans += recursion(1, length, a);
++a[i];
}
return ans;
}
int numTilePossibilities(string tiles) {
int a[26] = {0};
for (char c : tiles) ++a[c-'A'];
int ans = 0;
for (int i = 0; i < 26; ++i) {
if (a[i] == 0) continue;
--a[i];
++ans;
ans += recursion(1, tiles.size(), a);
++a[i];
}
return ans;
}
};