Skip to content

← leetcode

Letter Tile Possibilities

· Medium

LeetCode problem 1079

This week seems to be the week of the backtracking.

A simple recursion algorithm would suffice; just create an array of size 26 to hold the count of each letter of the alphabet, and iterate through all possibilities at each index.

code

class Solution {
public:
    int recursion(int index, int length, int *a) {
        if (index == length) return 0;
        int ans = 0;
        for (int i = 0; i < 26; ++i) {
            if (a[i] == 0) continue;
            --a[i];
            ++ans;
            ans += recursion(1, length, a);
            ++a[i];
        }
        return ans;
    }
    int numTilePossibilities(string tiles) {
        int a[26] = {0};
        for (char c : tiles) ++a[c-'A'];
        int ans = 0;
        for (int i = 0; i < 26; ++i) {
            if (a[i] == 0) continue;
            --a[i];
            ++ans;
            ans += recursion(1, tiles.size(), a);
            ++a[i];
        }
        return ans;
    }
};

complexity

  • Time: O(2^n)
  • Space: O(n)

learnings

  • if you want to pass an integer array as an argument into a function, it's type is just int *a since that just points to the first index in the array.

time taken

  • 13 minutes and 8.04 seconds
    • realistically took me ~6 minutes but I forgot how typing works