Permutation with no Repetition
This is a classic problem with a well-established technique for solving it. Comes from Leetcode:
https://leetcode.com/problems/letter-tile-possibilities/
- Do a standard DFS using the "output position" to control the recursion
- Have a global hash table tracking the index that has already been used
- Have a local hash table tracking the character that has already been used
- That's all
Code's below. Cheers, ACC.
https://leetcode.com/problems/letter-tile-possibilities/
You have a set of
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.
Example 1:
Input: "AAB" Output: 8 Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".
Example 2:
Input: "AAABBC" Output: 188
Note:
1 <= tiles.length <= 7
tiles
consists of uppercase English letters.
- Do a standard DFS using the "output position" to control the recursion
- Have a global hash table tracking the index that has already been used
- Have a local hash table tracking the character that has already been used
- That's all
Code's below. Cheers, ACC.
public class Solution { public int NumTilePossibilities(string tiles) { int num = 0; NumTilePossibilities(tiles, 0, new Hashtable(), ref num); return num; } private void NumTilePossibilities(string tiles, int currentPosition, Hashtable indexUsed, ref int num) { if (currentPosition >= tiles.Length) { return; } Hashtable charUsed = new Hashtable(); for (int i = 0; i < tiles.Length; i++) { if (!indexUsed.ContainsKey(i) && !charUsed.ContainsKey(tiles[i])) { num++; indexUsed.Add(i, true); charUsed.Add(tiles[i], true); NumTilePossibilities(tiles, currentPosition + 1, indexUsed, ref num); if (indexUsed.ContainsKey(i)) indexUsed.Remove(i); } } } }
Very nice! You can significantly speed this up by using a 26 element array of booleans instead of Hashtables for indexUsed and charUsed. I have decided to store counts of characters and at each iteration using one of the available ones:
ReplyDeleteclass Solution {
private:
static const int ALPHABET_SIZE = 26;
using Counts = array;
int explore(Counts& counts) {
int ways = 0;
for (int i = 0; i < ALPHABET_SIZE; ++i) {
if (counts[i] < 1) continue;
counts[i] -= 1;
ways += 1 + explore(counts);
counts[i] += 1;
}
return ways;
}
public:
int numTilePossibilities(string tiles) {
Counts counts {0};
for (char ch : tiles) counts[ch - 'A'] += 1;
return explore(counts);
}
};