README.md

1079. 活字印刷

English Version

题目描述

你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

注意：本题中，每个活字字模只能使用一次。

 

示例 1：

输入："AAB"
输出：8
解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。

示例 2：

输入："AAABBC"
输出：188

示例 3：

输入："V"
输出：1

 

提示：

• 1 <= tiles.length <= 7
• tiles 由大写英文字母组成

解法

Python3

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        def dfs():
            ans = 0
            for i in range(26):
                if cnt[i]:
                    ans += 1
                    cnt[i] -= 1
                    ans += dfs()
                    cnt[i] += 1
            return ans

        cnt = [0] * 26
        for t in tiles:
            cnt[ord(t) - ord('A')] += 1
        return dfs()

Java

class Solution {
    public int numTilePossibilities(String tiles) {
        int[] cnt = new int[26];
        for (char c : tiles.toCharArray()) {
            ++cnt[c - 'A'];
        }
        return dfs(cnt);
    }

    private int dfs(int[] cnt) {
        int res = 0;
        for (int i = 0; i < cnt.length; ++i) {
            if (cnt[i] > 0) {
                ++res;
                --cnt[i];
                res += dfs(cnt);
                ++cnt[i];
            }
        }
        return res;
    }
}

C++

class Solution {
public:
    int numTilePossibilities(string tiles) {
        vector<int> cnt(26);
        for (char& c : tiles) ++cnt[c - 'A'];
        return dfs(cnt);
    }

    int dfs(vector<int>& cnt) {
        int res = 0;
        for (int i = 0; i < 26; ++i) {
            if (cnt[i]) {
                --cnt[i];
                ++res;
                res += dfs(cnt);
                ++cnt[i];
            }
        }
        return res;
    }
};

Go

func numTilePossibilities(tiles string) int {
	cnt := make([]int, 26)
	for _, c := range tiles {
		cnt[c-'A']++
	}
	var dfs func() int
	dfs = func() int {
		res := 0
		for i := 0; i < 26; i++ {
			if cnt[i] > 0 {
				res++
				cnt[i]--
				res += dfs()
				cnt[i]++
			}
		}
		return res
	}
	return dfs()
}

...