1079. Letter Tile Possibilities #

Problem #

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.

Problem Summary #

You have a set of letter tiles tiles, where each tile has one letter tiles[i] engraved on it. Return the number of non-empty letter sequences you can print. Note:

1 <= tiles.length <= 7
tiles consists of uppercase English letters

Solution Approach #

The problem asks for the number of all non-empty letter sequences. This problem is a combination of permutations and combinations. For combinations, you can choose one letter, two letters, …… n letters. Within each combination, it is a permutation problem. For example, when choosing 2 letters, different orders between the letters affect the final result, and different permutation orders are different solutions.
Since this problem does not require outputting all solutions, the solution can be optimized. For example, when recursively calculating the answer, we do not need to actually traverse the original string; we only need to accumulate the frequencies of some letters. Of course, if we want to output all solutions, we need to actually traverse the original string (see Solution 2). A simple approach is to accumulate according to frequency in each recursion. Because each time we add a letter, it must be one of the 26 uppercase letters. What needs attention here is that the added letter can only be a letter among the 26 letters that still has remaining “opportunities” to be taken. For example, when the recursion reaches the 3rd round and A has been used up, at this point we can only take letters whose frequencies are not 0 and append them.

Code #


package leetcode

// Solution 1 DFS
func numTilePossibilities(tiles string) int {
	m := make(map[byte]int)
	for i := range tiles {
		m[tiles[i]]++
	}
	arr := make([]int, 0)
	for _, v := range m {
		arr = append(arr, v)
	}
	return numTileDFS(arr)
}

func numTileDFS(arr []int) (r int) {
	for i := 0; i < len(arr); i++ {
		if arr[i] == 0 {
			continue
		}
		r++
		arr[i]--
		r += numTileDFS(arr)
		arr[i]++
	}
	return
}

// Solution 2 DFS brute-force solution
func numTilePossibilities1(tiles string) int {
	res, tmp, tMap, used := 0, []byte{}, make(map[string]string, 0), make([]bool, len(tiles))
	findTile([]byte(tiles), tmp, &used, 0, &res, tMap)
	return res
}

func findTile(tiles, tmp []byte, used *[]bool, index int, res *int, tMap map[string]string) {
	flag := true
	for _, v := range *used {
		if v == false {
			flag = false
			break
		}
	}
	if flag {
		return
	}
	for i := 0; i < len(tiles); i++ {
		if (*used)[i] == true {
			continue
		}
		tmp = append(tmp, tiles[i])
		(*used)[i] = true
		if _, ok := tMap[string(tmp)]; !ok {
			//fmt.Printf("i = %v tiles = %v found result = %v\n", i, string(tiles), string(tmp))
			*res++
		}
		tMap[string(tmp)] = string(tmp)

		findTile([]byte(tiles), tmp, used, i+1, res, tMap)
		tmp = tmp[:len(tmp)-1]
		(*used)[i] = false
	}
}