题目地址:https://leetcode.com/problems/letter-tile-possibilities/

题目描述

Youhave a set of 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.

Example 1:

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

Example 2:

Input: "AAABBC"
Output: 188

Note:

1、 1<=tiles.length<=7
2、 tilesconsistsofuppercaseEnglishletters.;

题目大意

给出了一些活字印刷的模具,看能组合成多少种不同的单词。

解题方法

回溯

又是一个经典的回溯法。

让我们先看下AAB能构成的结果:

A           // 剩余A、B
AA AB       // 剩余B,剩余A
AAB ABA     // 不剩

B           // 剩余A、A
BA          // 剩余A
BAA         // 不剩

我们可以发现,先选择一个字母开始,然后从剩余的字母里选择1个、2个...直至用完所有字母,放到了第一个字母的后面。

因此是一个递归的方法,先统计每个字母出现的多少次,然后从中选择一个字母,再从剩下的字母中选择,直至所有字母都用完为止。

这里回溯的含义是,我们使用了个数组保存每个字母出现的次数,每次拼接上一个新的字母的时候,把结果res就加一,同时把对应的字母出现的次数减一;当把剩余的结果递归完成之后,需要把当前的字母的次数加上,以便后续的遍历,故称为回溯。

那为什么使用统计字母出现的次数,而不是直接在原来的单词上选择呢?好处是,这样同样的字母在同样的位置只会被选择一次。比如AAB的第一个A和第二个A都可以组成AB,如果在单词上选可能需要set进行去重,但是统计字母出现的次数的时候,在第一个位置选择A的时候只会选择一次。

C++代码如下:

class Solution {
public:
    int numTilePossibilities(string tiles) {
        vector<int> count(26, 0);
        for (char c : tiles) {
            count[c - 'A'] ++;
        }
        int res = 0;
        backtrack(count, res);
        return res;
    }
    void backtrack(vector<int>& count, int& res) {
        for (int i = 0; i < 26; ++i) {
            if (count[i] == 0) continue;
            res ++;
            count[i] --;
            backtrack(count, res);
            count[i] ++;
        }
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

2022

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发