Comment on page
1079.Letter Tile Possibilities
1079.Letter Tile Possibilities
难度:Medium
你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
示例 1：
输入："AAB"
输出：8
解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。
示例 2：
输入："AAABBC"
输出：188
提示：
1 <= tiles.length <= 7
tiles 由大写英文字母组成
树形结构，递归求解，首先需要确定不同的字符数，可以使用map来统计，递归终止条件，是某个字符出现次数为0，此时到达叶子节点，统计整个数的节点数目即为所求。
class Solution {
int cnt=0;
void numTile(unordered_map<char, int> alpha)
{
for(auto a:alpha)
{
if(a.second)
{
cnt++;
unordered_map<char, int>tmp(alpha);
tmp[a.first]--;
numTile(tmp);
}
}
}
public:
int numTilePossibilities(string tiles) {
unordered_map<char,int>alpha;
for(auto t:tiles)
alpha[t]++;
numTile(alpha);
return cnt;
}
};
执行用时 :268 ms, 在所有 C++ 提交中击败了10.83%的用户 内存消耗 :74.5 MB, 在所有 C++ 提交中击败了100.00%的用户
Last modified 1yr ago