LeetCode 解題紀錄 1079. Letter Tile Possibilities

Letter Tile Possibilities - LeetCode

題目

你有 n 個壁磚，壁磚上有一個大寫英文字母，返回不重複的字串總數

限制

• 1 ≤ tiles.length ≤ 7

觀察

• 要找出所有的排列組合，可以使用 backtracking
• 使用陣列來計數每個字母，每次遞迴一個字母只會選擇一次，這樣可以避免重複發生

解法 1 (Backtracking + Counting Sort)

• 將字母出現的次數做統計
• 使用次數陣列當作遞迴參數，每次從 26 個字母中選擇還未被選走的
• 每選走一個增加一次，這個字母加上遞迴後新的字串會再產生新字串，所以再加上遞迴返回的結果

class Solution {
    public int numTilePossibilities(String tiles) {
        int freq[] = new int[26];
        for(char c:tiles.toCharArray())
            freq[c-'A']++;
        return dfs(freq);
    }

    int dfs(int[] freq) {
        int count = 0;
        for(int i=0;i<freq.length;i++) {
            if(freq[i] > 0) {
                freq[i]--;
                count += dfs(freq)+1;
                freq[i]++;
            }
        }
        return count;
    }
}

結果

TC：O(n!)，SC：O(log n)