回溯法实现:
class Solution {
public:
int numTilePossibilities(string tiles) {
vector<int> record(26,0);
for(auto c:tiles)
{
record[c-'A']++;
}
return dfs(record);
}
private:
int dfs(vector<int>& record) {
int sum = 0;
for(int i = 0;i < record.size();i++)
{
if(record[i] == 0) continue;
sum++;
record[i]--;
sum += dfs(record);
record[i]++;
}
return sum;
}
};
运行效率:
Runtime: 8 ms, faster than 72.86% of C++ online submissions for Letter Tile Possibilities.
Memory Usage: 5.9 MB, less than 86.96% of C++ online submissions for Letter Tile Possibilities
非常详细的解释:1079. Letter Tile Possibilities