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 <= 7tiles consists of uppercase English letters.
Solutions
Solution 1
PythonJavaC++GoTypeScript
class Solution:
def numTilePossibilities(self, tiles: str) -> int:
def dfs(cnt: Counter) -> int:
ans = 0
for i, x in cnt.items():
if x > 0:
ans += 1
cnt[i] -= 1
ans += dfs(cnt)
cnt[i] += 1
return ans
cnt = Counter(tiles)
return dfs(cnt)(code-box)
class Solution {
public int numTilePossibilities(String tiles) {
int[] cnt = new int[26];
for (char c : tiles.toCharArray()) {
++cnt[c - 'A'];
}
return dfs(cnt);
}
private int dfs(int[] cnt) {
int res = 0;
for (int i = 0; i < cnt.length; ++i) {
if (cnt[i] > 0) {
++res;
--cnt[i];
res += dfs(cnt);
++cnt[i];
}
}
return res;
}
}(code-box)
class Solution {
public:
int numTilePossibilities(string tiles) {
int cnt[26]{};
for (char c : tiles) {
++cnt[c - 'A'];
}
function<int(int* cnt)> dfs = [&](int* cnt) -> int {
int res = 0;
for (int i = 0; i < 26; ++i) {
if (cnt[i] > 0) {
++res;
--cnt[i];
res += dfs(cnt);
++cnt[i];
}
}
return res;
};
return dfs(cnt);
}
};(code-box)
func numTilePossibilities(tiles string) int {
cnt := [26]int{}
for _, c := range tiles {
cnt[c-'A']++
}
var dfs func(cnt [26]int) int
dfs = func(cnt [26]int) (res int) {
for i, x := range cnt {
if x > 0 {
res++
cnt[i]--
res += dfs(cnt)
cnt[i]++
}
}
return
}
return dfs(cnt)
}(code-box)
function numTilePossibilities(tiles: string): number {
const cnt: number[] = new Array(26).fill(0);
for (const c of tiles) {
++cnt[c.charCodeAt(0) - 'A'.charCodeAt(0)];
}
const dfs = (cnt: number[]): number => {
let res = 0;
for (let i = 0; i < 26; ++i) {
if (cnt[i] > 0) {
++res;
--cnt[i];
res += dfs(cnt);
++cnt[i];
}
}
return res;
};
return dfs(cnt);
}(code-box)
