Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

1079. Letter Tile Possibilities

Time: $O(n^{26})$

Space: $O(n)$

			


class Solution {
 public:
  int numTilePossibilities(string tiles) {
    vector<int> count(26);

    for (const char t : tiles)
      ++count[t - 'A'];

    return dfs(count);
  }

 private:
  int dfs(vector<int>& count) {
    int possibleSequences = 0;

    for (int& c : count) {
      if (c == 0)
        continue;
      // Put c in the current position. We only care about the # of possible
      // sequences of letters but don't care about the actual combination.
      --c;
      possibleSequences += 1 + dfs(count);
      ++c;
    }

    return possibleSequences;
  }
};




			


class Solution {
  public int numTilePossibilities(String tiles) {
    int[] count = new int[26];

    for (final char t : tiles.toCharArray())
      ++count[t - 'A'];

    return dfs(count);
  }

  private int dfs(int[] count) {
    int possibleSequences = 0;

    for (int i = 0; i < 26; ++i) {
      if (count[i] == 0)
        continue;
      // Put c in the current position. We only care about the # of possible
      // sequences of letters but don't care about the actual combination.
      --count[i];
      possibleSequences += 1 + dfs(count);
      ++count[i];
    }

    return possibleSequences;
  }
}




			


class Solution:
  def numTilePossibilities(self, tiles: str) -> int:
    count = Counter(tiles)

    def dfs(count: Dict[int, int]) -> int:
      possibleSequences = 0

      for k, v in count.items():
        if v == 0:
          continue
        # Put c in the current position. We only care about the # of possible
        # sequences of letters but don't care about the actual combination.
        count[k] -= 1
        possibleSequences += 1 + dfs(count)
        count[k] += 1

      return possibleSequences

    return dfs(count)