Letter Tile Possibilities
Similar Problems:
- Tag: #subset, #backtracking, #dfs, #classic
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.
Github: code.dennyzhang.com
Credits To: leetcode.com
Leave me comments, if you have better ways to solve.
- Solution:
// Blog link: https://code.dennyzhang.com/letter-tile-possibilities // Basic Ideas: Permutation with duplicate elements // // Complexity: Time ?, Space ? import "sort" func dfs(chars []int, l []int, items []byte, pos int) int { res := 0 // Combination with current setup count, val := 0, 1 for _, v := range chars { if v != 0 { count += v val *= l[v] } } if count != 0 { res += l[count]/val } for i:=pos; i<len(items); i++ { if (i>pos) && (items[i-1] == items[i]) { continue } j := items[i]-'A' chars[j]++ res += dfs(chars, l, items, i+1) chars[j]-- } return res } func numTilePossibilities(tiles string) int { l := []int{1, 1, 2, 6, 24, 120, 720, 5040} items := []byte(tiles) sort.Slice(items, func(i, j int) bool { return items[i] < items[j] }) chars := make([]int, 26) return dfs(chars, l, items, 0) }
Share It, If You Like It.