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.
使用递归解法
class Solution {
public int numTilePossibilities(String tiles) {
char[] chars = tiles.toCharArray();
List cahrArray = new LinkedList();
for(int i=0;i<chars.length;i++){
cahrArray.add(chars[i]);
}
Map strMap = new HashMap();
String str = "";
checkStr( str, strMap, cahrArray);
return strMap.size();
}
public void checkStr(String str, Map strMap, List chars){
if(chars.size()!=0){
for(int i=0;i<chars.size();i++){
char s = (char)chars.get(i);
String newstr = str + s;
strMap.put(newstr,null);
chars.remove(i);
checkStr(newstr,strMap,chars);
chars.add(i,s);
}
}
}
}
效果不理想，速度很慢
Runtime: 25 ms, faster than 32.91% of Java online submissions for Letter Tile Possibilities.
Memory Usage: 38.3 MB, less than 100.00% of Java online submissions for Letter Tile Possibilities.
优化一：将LinkedList修改为ArrayList，也就快乐一点点
Runtime: 20 ms, faster than 39.12% of Java online submissions for Letter Tile Possibilities.
Memory Usage: 36.8 MB, less than 100.00% of Java online submissions for Letter Tile Possibilities.
优化二：判断重复前缀不需要递归
public void checkStr(String str, Map strMap, List chars){
if(chars.size()!=0){
for(int i=0;i<chars.size();i++){
char s = (char)chars.get(i);
String newstr = str + s;
if(strMap.containsKey(newstr)){
continue;
}
strMap.put(newstr,null);
chars.remove(i);
checkStr(newstr,strMap,chars);
chars.add(i,s);
}
}
}
Runtime: 15 ms, faster than 45.99% of Java online submissions for Letter Tile Possibilities.
Memory Usage: 38.3 MB, less than 100.00% of Java online submissions for Letter Tile Possibilities.
目前发现网友最优算法
思路：使用26字母的数组统计字符出现次数，大致原来跟我设计差不多，通过对应字母--和++实现使用和还原。
但是目前疑问就是为什么不判断重复字符串问题呢？直接就总返回值+1？
答案：其实很简单，由于采用该数组模式，相同字母只会取一次作为前缀拼接。
这个相当于我们之前Map判断是否存在一样。
public int numTilePossibilities(String tiles) {
int[] count = new int[26];
for (char c : tiles.toCharArray()) count[c - 'A']++;
return dfs(count);
}
int dfs(int[] arr) {
int sum = 0;
for (int i = 0; i < 26; i++) {
if (arr[i] == 0) continue;
sum++;
arr[i]--;
sum += dfs(arr);
arr[i]++;
}
return sum;
}
Runtime: 1 ms, faster than 99.15% of Java online submissions for Letter Tile Possibilities.
Memory Usage: 34.2 MB, less than 100.00% of Java online submissions for Letter Tile Possibilities.
