题目链接

Leetcode.1079 活字印刷 Rating ： 1741

题目描述

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

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

示例 1：

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

示例 2：

输入：“AAABBC”
输出：188

示例 3：

输入：“V”
输出：1

提示：

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

解法：回溯

我们先模拟一下 {A,A,B}。

绿色的集合都是合法的方案。

我们发现只要同一层中不出现重复的字符，就不会有重复的方案。

我们用一个 布尔数组 vis来记录每个字符的被选择情况。

所以我们每次遇到重复的字符，都直接跳过。为了方便处理，我们可以将原串 tiles先排序。用一个变量 last记录上一次选择的字符，当前字符 s[u]和 last相同，就要跳过当前字符 s[u]的递归，再判断 s[u+1]。

时间复杂度： O(n!+nlogn)O(n! + nlogn)O(n!+nlogn)

C++代码：

class Solution {
public:int n,ans = 0;void dfs(string& s,vector& vis){char last = '#';for(int i = 0;i < n;i++){if(!vis[i] && s[i] != last){ans++;vis[i] = true;dfs(s,vis);vis[i] = false;last = s[i];}}}int numTilePossibilities(string tiles) {n = tiles.size();vector vis(n);sort(tiles.begin(),tiles.end());dfs(tiles,vis);return ans;}
};