Question

1079. Letter Tile Possibilities

中文文档

Description

You have n  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 using the letters printed on those tiles.

 

Example 1:

Input: tiles = "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2:

Input: tiles = "AAABBC"
Output: 188

Example 3:

Input: tiles = "V"
Output: 1

 

Constraints:

• 1 <= tiles.length <= 7
• tiles consists of uppercase English letters.

Solutions

Solution 1

class Solution:
  def numTilePossibilities(self, tiles: str) -> int:
    def dfs(cnt: Counter) -> int:
      ans = 0
      for i, x in cnt.items():
        if x > 0:
          ans += 1
          cnt[i] -= 1
          ans += dfs(cnt)
          cnt[i] += 1
      return ans

    cnt = Counter(tiles)
    return dfs(cnt)

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

  private int dfs(int[] cnt) {
    int res = 0;
    for (int i = 0; i < cnt.length; ++i) {
      if (cnt[i] > 0) {
        ++res;
        --cnt[i];
        res += dfs(cnt);
        ++cnt[i];
      }
    }
    return res;
  }
}

class Solution {
public:
  int numTilePossibilities(string tiles) {
    int cnt[26]{};
    for (char c : tiles) {
      ++cnt[c - 'A'];
    }
    function<int(int* cnt)> dfs = [&](int* cnt) -> int {
      int res = 0;
      for (int i = 0; i < 26; ++i) {
        if (cnt[i] > 0) {
          ++res;
          --cnt[i];
          res += dfs(cnt);
          ++cnt[i];
        }
      }
      return res;
    };
    return dfs(cnt);
  }
};

func numTilePossibilities(tiles string) int {
  cnt := [26]int{}
  for _, c := range tiles {
    cnt[c-'A']++
  }
  var dfs func(cnt [26]int) int
  dfs = func(cnt [26]int) (res int) {
    for i, x := range cnt {
      if x > 0 {
        res++
        cnt[i]--
        res += dfs(cnt)
        cnt[i]++
      }
    }
    return
  }
  return dfs(cnt)
}

function numTilePossibilities(tiles: string): number {
  const cnt: number[] = new Array(26).fill(0);
  for (const c of tiles) {
    ++cnt[c.charCodeAt(0) - 'A'.charCodeAt(0)];
  }
  const dfs = (cnt: number[]): number => {
    let res = 0;
    for (let i = 0; i < 26; ++i) {
      if (cnt[i] > 0) {
        ++res;
        --cnt[i];
        res += dfs(cnt);
        ++cnt[i];
      }
    }
    return res;
  };
  return dfs(cnt);
}