1079. 活字印刷

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

 

示例 1:

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

输入:"AAABBC"
输出:188
 

提示:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/letter-tile-possibilities
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

 

和90.子集II一类题,难点在于如何保证结果不重复。

 

 1 public class Solution {
 2     private char[] titles = null;
 3     private int count = 0;
 4     private boolean[] flag = null;
 5     private int len = -1;
 6 
 7     private void helper(){
 8 
 9         for (int i = 0; i < len; i++) {
10             if (!flag[i]){
11                 ++count;
12                 flag[i] = true;
13                 helper();
14                 flag[i] = false;
15                 while (i+1<len && titles[i] == titles[i+1]) ++i;
16             }
17         }
18     }
19 
20     public int numTilePossibilities(String tiles) {
21         this.titles = tiles.toCharArray();
22         len = tiles.length();
23         flag = new boolean[len];
24         Arrays.sort(this.titles);
25         helper();
26         return count;
27     }
28 
29     public static void main(String[] args) {
30         int aa = new Solution().numTilePossibilities("AAAB");
31         System.out.println("aa = " + aa);
32     }
33 }

 

上一篇:浙大 PAT 甲级 1079 Total Sales of Supply Chain 最简单的深度优先搜索 DFS


下一篇:1079 延迟的回文数