1079. Letter Tile Possibilities
https://leetcode.com/problems/letter-tile-possibilities/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.
------------
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int numTilePossibilities(String tiles) { | |
| int[] counts = new int[26]; | |
| for (char ch: tiles.toCharArray()) { | |
| counts[ch - 'A']++; | |
| } | |
| return dfs(counts); | |
| } | |
| private int dfs(int[] counts) { | |
| int ans = 0; | |
| for (int i = 0; i < counts.length; i++) { | |
| // skip characters not present | |
| if (counts[i] == 0) { | |
| continue; | |
| } | |
| // use current character | |
| ans++; | |
| counts[i]--; | |
| // recurse | |
| ans += dfs(counts); | |
| // backtrack, do not use current char | |
| counts[i]++; | |
| } | |
| return ans; | |
| } | |
| } |
