1079. Letter Tile Possibilities

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.

Rust Solution

struct Solution;

impl Solution {
    fn num_tile_possibilities(tiles: String) -> i32 {
        let mut counts: Vec<usize> = vec![0; 26];
        for c in tiles.chars() {
            counts[(c as u8 - b'A') as usize] += 1;
        }
        let mut res = 0;
        Self::dfs(&mut res, &mut counts);
        res
    }

    fn dfs(sum: &mut i32, counts: &mut Vec<usize>) {
        for i in 0..26 {
            if counts[i] > 0 {
                *sum += 1;
                counts[i] -= 1;
                Self::dfs(sum, counts);
                counts[i] += 1;
            }
        }
    }
}

#[test]
fn test() {
    let tiles = "AAB".to_string();
    let res = 8;
    assert_eq!(Solution::num_tile_possibilities(tiles), res);
    let tiles = "AAABBC".to_string();
    let res = 188;
    assert_eq!(Solution::num_tile_possibilities(tiles), res);
}

Having problems with this solution? Click here to submit an issue on github.