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