Description
You have n tiles, where each tile has one letter tiles[i] printed on it.
Return the number of possible non-empty sequences of letters you can make using the letters printed on those tiles.
Example 1:
Input: tiles = "AAB" Output: 8 Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA". Example 2:
Input: tiles = "AAABBC" Output: 188 Example 3:
Input: tiles = "V" Output: 1 Constraints:
1 <= tiles.length <= 7tilesconsists of uppercase English letters.
这道题给了一个字符串，让求出所有不同排列方式的非空子序列的个数。博主最开始做的时候以为是跟之前那道 Permutations II 一样，是求有重复数字的全排列。但是这里求的不止是全排列，还有子序列的全排列，情况更多，不过好就好在不用返回所有的情况，而是返回总个数即可。这里还是需要用递归来做，由于可能存在大量的重复的字母，所以比较好的方法就是统计每个字母出现的次数，使用 HashMap 或者一个大小为 26 的数组。因为题目中限定了只有大写字母，所以用一个带大小为 26 的数组 cnt 更加省事。统计好了字母出现的次数之和，就可以对 cnt 数组调用递归了。在递归函数中，遍历每个字母，若其出现次数为0，则直接跳过。否则结果 res 自增1，因为加上一个当前字母就会形成一种新的排列方式。然后该字母的映射值减1，之后再对于更新后的 cnt 数组调用递归函数，将返回值加到结果 res 之中。之后要还原状态，即将当前的出现次数再加回1，参见代码如下：
class Solution { public: int numTilePossibilities(string tiles) { vector<int> cnt(26); for (char c : tiles) ++cnt[c - 'A']; return helper(cnt); } int helper(vector<int>& cnt) { int res = 0; for (int i = 0; i < 26; ++i) { if (cnt[i] == 0) continue; ++res; --cnt[i]; res += helper(cnt); ++cnt[i]; } return res; } }; Github 同步地址:
参考资料：
https://leetcode.com/problems/letter-tile-possibilities/
https://leetcode.com/problems/letter-tile-possibilities/discuss/308284/Concise-java-solution