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.
優(yōu)化一：將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.
優(yōu)化二：判斷重復(fù)前綴不需要遞歸
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.
目前發(fā)現(xiàn)網(wǎng)友最優(yōu)算法
思路：使用26字母的數(shù)組統(tǒng)計字符出現(xiàn)次數(shù)菇存，大致原來跟我設(shè)計差不多，通過對應(yīng)字母--和++實現(xiàn)使用和還原骚揍。
但是目前疑問就是為什么不判斷重復(fù)字符串問題呢？直接就總返回值+1啰挪？
答案：其實很簡單信不，由于采用該數(shù)組模式，相同字母只會取一次作為前綴拼接亡呵。
這個相當于我們之前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.
