LeetCode: Letter Tile Possibilities Posted on August 12, 2019July 26, 2020 by braindenny Letter Tile Possibilities Similar Problems: LeetCode: Subsets II CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups 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: // 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) } Post Views: 0