1079. Letter Tile Possibilities #1326
-
Topics: You have Return the number of possible non-empty sequences of letters you can make using the letters printed on those Example 1:
Example 2:
Example 3:
Constraints:
Hint:
|
Beta Was this translation helpful? Give feedback.
Replies: 1 comment 2 replies
-
We need to determine the number of distinct non-empty sequences that can be formed using the letters from a given set of tiles. Each tile has a letter printed on it, and sequences are considered distinct based on the order of letters, even if they use the same letters from different tiles. ApproachThe approach involves using backtracking to generate all possible permutations of the tiles for all possible lengths from 1 to the length of the tiles string. We use a frequency map to keep track of the count of each letter and ensure that we do not generate duplicate sequences by carefully managing the counts of each letter during the backtracking process.
Let's implement this solution in PHP: 1079. Letter Tile Possibilities <?php
/**
* @param String $tiles
* @return Integer
*/
function numTilePossibilities($tiles) {
$counts = array_count_values(str_split($tiles));
$total = 0;
for ($k = 1; $k <= strlen($tiles); $k++) {
$currentResult = 0;
backtrack($counts, $k, 0, $currentResult);
$total += $currentResult;
}
return $total;
}
/**
* @param $counts
* @param $k
* @param $currentLength
* @param $result
* @return void
*/
function backtrack(&$counts, $k, $currentLength, &$result) {
if ($currentLength == $k) {
$result++;
return;
}
foreach (array_keys($counts) as $char) {
if ($counts[$char] == 0) {
continue;
}
$counts[$char]--;
backtrack($counts, $k, $currentLength + 1, $result);
$counts[$char]++;
}
}
// Test Cases
echo numTilePossibilities("AAB") . "\n"; // Output: 8
echo numTilePossibilities("AAABBC") . "\n"; // Output: 188
echo numTilePossibilities("V") . "\n"; // Output: 1
?> Explanation:
This approach efficiently avoids generating duplicate sequences by managing the counts of each character and ensuring each permutation is unique through careful backtracking. The complexity is manageable due to the constraint of the input length being up to 7, making the backtracking approach feasible. |
Beta Was this translation helpful? Give feedback.
We need to determine the number of distinct non-empty sequences that can be formed using the letters from a given set of tiles. Each tile has a letter printed on it, and sequences are considered distinct based on the order of letters, even if they use the same letters from different tiles.
Approach
The approach involves using backtracking to generate all possible permutations of the tiles for all possible lengths from 1 to the length of the tiles string. We use a frequency map to keep track of the count of each letter and ensure that we do not generate duplicate sequences by carefully managing the counts of each letter during the backtracking process.