Letter Tile Possibilities

Leetcode Problem:

• Letter Tile Possibilities

Summary

• The problem is to find the number of possible non-empty sequences of letters that can be made using the letters printed on the tiles.

Approach

• The solution uses a recursive approach with backtracking
• It checks all possible combinations of letters and stores the valid sequences in a set.

Complexity

• O(2^n * n) where n is the length of the tiles string

Explanation

• The solution uses a recursive function checkCnt to generate all possible sequences of letters
• It uses a set to store the valid sequences and a visited array to prevent duplicate sequences
• The function checks all possible combinations of letters and adds the valid sequences to the set
• Finally, it returns the size of the set, which represents the number of possible non-empty sequences of letters.

Solution Code:

class Solution {
public:
    bool visited[7];
    set s;
    void checkCnt(string &tiles, string letters, int length, int depth){
        if(length == depth){
            s.insert(letters);
            return;
        }
        for(int i = 0 ; i < tiles.size(); i++){
            if(visited[i]) continue;
            visited[i] = true;
            checkCnt(tiles, letters + tiles[i], length + 1, depth);
            visited[i] = false;
        }
    }   
    int numTilePossibilities(string tiles) {
        for(int i = 1; i <= tiles.size(); i++){
            checkCnt(tiles, "", 0, i);
        }
        return s.size();
    }
};