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 <= 7
tiles consists of uppercase English letters.
Solution:
class Solution {
public int numTilePossibilities(String tiles) {
char[] arr = tiles.toCharArray();
Set<String> set = new HashSet();
helper(arr, 0, set, new StringBuilder());
// System.out.println(set);
return set.size();
}
private void helper(char[] arr, int i, Set<String> set, StringBuilder sb) {
if (i == arr.length) {
if (sb.length() > 0) {
set.add(sb.toString());
}
return;
}
for (int j = i; j < arr.length; j ++) {
swap(arr, i, j);
helper(arr, i + 1, set, sb);
sb.append(arr[i]);
helper(arr, i + 1, set, sb);
sb.deleteCharAt(sb.length() - 1);
swap(arr, i, j);
}
}
private void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Thoughts
input: AAB count: A -> 2, B -> 1
For sequence of length 1:
We can pick either A, or B.
So we have "A", "B".
For sequence of length 2:
We build it based on "sequence of length 1"
For "A":
count: A -> 1, B -> 1
We can still pick either A, or B
So we have "AA", "AB"
For "B":
count: A -> 2, B -> 0
We can only pick A
So we have "BA"
For sequence of length 3: blablabla
Implementation
We don't need to keep track of the sequence. We only need count
If we implement the above idea by each level (Count all sequence of length 1, then count all sequence of length 2, etc), we have to remember previous sequence.
So we use recursion instead. Just remember to add the count back (arr[i]++).
public int numTilePossibilities(String tiles) {
int[] count = new int[26];
for (char c : tiles.toCharArray()) count[c - 'A']++;
return dfs(count);
}
int dfs(int[] arr) {
int sum = 0;
for (int i = 0; i < 26; i++) {
if (arr[i] == 0) continue;
sum++;
arr[i]--;
sum += dfs(arr);
arr[i]++;
}
return sum;
}