# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# + active=""
# 说明：
#     你有n个 tiles，每个tiles上都印着一个字母。返回使用这些平铺上打印的字母可以生成的非空字母序列数。
#    
# 要求：
#     使用给定的 S，返回由S可以组成字符串的最大数量。不能重复。
#
# 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
# -

# 虽然可以通过，但是时间复杂度较高
class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        self.res = []
        for i in range(len(tiles)):
            self.dfs(tiles[:i] + tiles[i+1:], tiles[i])
        return len(self.res)
        
    def dfs(self, tiles, temp):
        if temp not in self.res:
            self.res.append(temp[:])
        for i in range(len(tiles)):
            self.dfs(tiles[:i] + tiles[i+1:], temp+tiles[i])



tiles_ = "AAABBC"
solution = Solution()
solution.numTilePossibilities(tiles_)



StarcoderdataJupyterScriptsDedupFiltered