你有一套活字字模 tiles,其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
注意:本题中,每个活字字模只能使用一次。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/letter-tile-possibilities
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
回溯
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
class Solution {
private int solve(Map<Character, Integer> cntMap, Set<Character> characterSet, int n) {
if (n == 0) {
return 1;
}
int result = 1;
for (Character character : characterSet) {
if (cntMap.get(character) > 0) {
cntMap.merge(character, -1, Integer::sum);
result += solve(cntMap, characterSet, n - 1);
cntMap.merge(character, 1, Integer::sum);
}
}
return result;
}
public int numTilePossibilities(String tiles) {
if (tiles == null || tiles.length() == 0) {
return 0;
}
Map<Character, Integer> cntMap = new HashMap<>();
for (int i = 0; i < tiles.length(); i++) {
cntMap.merge(tiles.charAt(i), 1, Integer::sum);
}
Set<Character> characterSet = cntMap.keySet();
return solve(cntMap, characterSet, tiles.length()) - 1;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
System.out.println(new Solution().numTilePossibilities(in.next()));
}
}
}
DP
class Solution {
private static final int[][] c = new int[8][8];
static {
for (int i = 0; i < 8; i++) {
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; ++j) {
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
}
}
public int numTilePossibilities(String tiles) {
if (tiles == null || tiles.length() == 0) {
return 0;
}
Map<Character, Integer> cntMap = new HashMap<>();
for (int i = 0; i < tiles.length(); i++) {
cntMap.merge(tiles.charAt(i), 1, Integer::sum);
}
int m = cntMap.size();
int n = tiles.length();
int[][] f = new int[m + 1][n + 1];
f[0][0] = 1;
int i = 0;
for (int cnt : cntMap.values()) {
i++;
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= cnt && k <= j; k++) {
f[i][j] += f[i - 1][j - k] * c[j][k];
}
}
}
return Arrays.stream(f[m]).sum() - f[m][0];
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
System.out.println(new Solution().numTilePossibilities(in.next()));
}
}
}
标签:tiles,return,1079,int,length,活字印刷,cntMap,new
From: https://www.cnblogs.com/tianyiya/p/17415322.html