LeetCode: Letter Tile Possibilities

Posted on August 12, 2019July 26, 2020 by braindenny

Letter Tile Possibilities

Similar Problems:

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