Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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. 1 <= tiles.length <= 7
  2. 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)
}
linkedin
github
slack

Post Views: 0
Posted in BasicTagged #backtracking, #classic, #combination, #dfs, subset

Post navigation

LeetCode: Day of the Year
Review: DFS Problems

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.