活字印刷—Python递归与迭代解法

活字印刷

你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

注意：本题中，每个活字字模只能使用一次。

示例 1：
输入：“AAB”
输出：8
解释：可能的序列为 “A”, “B”, “AA”, “AB”, “BA”, “AAB”, “ABA”, “BAA”。

示例 2：
输入：“AAABBC”
输出：188

提示：
1 <= tiles.length <= 7
tiles 由大写英文字母组成

2. 求字母序列数目的Python代码

2.1 递归

def numTilePossibilities(tiles): result = 0 for i in set(tiles): result += 1 + numTilePossibilities(tiles.replace(i, '', 1)) return result print(numTilePossibilities('AAB')) print(numTilePossibilities('AABC')) print(numTilePossibilities('AAABBC')) 

实验结果：
8
34
188

代码解读：
函数numTilePossibilities是一个递归函数，参数tiles代表活字字模上的字母组成的字符串，返回值result代表使用tiles中的字母能够排列出多少种字符串。

递归子问题：从tiles中拿出1个字母i后，使用剩余字母能够排列出多少种字符串。该问题在代码中表达为：numTilePossibilities(tiles.replace(i, '', 1))。

若剩余字母排列出的字符串都加一个前缀i，即可得到一批新的字符串。由此可得，以字母i为前缀的字符串(包括字母i本身)共有1 + numTilePossibilities(tiles.replace(i, '', 1))种。

通过for i in set(tiles):遍历tiles去重后的字母集合，并使用result累计以不同字母为前缀的字符串的数目。

2.2 迭代

def numTilePossibilities(tiles): result = 0 stack = [tiles] while stack: tiles = stack.pop() for i in set(tiles): result += 1 stack.append(tiles.replace(i, '', 1)) return result print(numTilePossibilities('AAB')) print(numTilePossibilities('AABC')) print(numTilePossibilities('AAABBC')) 

实验结果：
8
34
188

3. 求字母序列的Python代码

3.1 递归

递归代码对解空间树的搜索是深度优先搜索(depth first search, dfs)。

def numTilePossibilities(tiles): result = [] def dfs(tiles, prefix): for i in sorted(set(tiles)): result.append(prefix+i) dfs(tiles.replace(i, '', 1), prefix+i) dfs(tiles, '') return result print(numTilePossibilities('AAB')) print(numTilePossibilities('AABC')) 

实验结果：
[‘A’, ‘AA’, ‘AAB’, ‘AB’, ‘ABA’, ‘B’, ‘BA’, ‘BAA’]
[‘A’, ‘AA’, ‘AAB’, ‘AABC’, ‘AAC’, ‘AACB’, ‘AB’, ‘ABA’, ‘ABAC’, ‘ABC’, ‘ABCA’, ‘AC’, ‘ACA’, ‘ACAB’, ‘ACB’, ‘ACBA’, ‘B’, ‘BA’, ‘BAA’, ‘BAAC’, ‘BAC’, ‘BACA’, ‘BC’, ‘BCA’, ‘BCAA’, ‘C’, ‘CA’, ‘CAA’, ‘CAAB’, ‘CAB’, ‘CABA’, ‘CB’, ‘CBA’, ‘CBAA’]

3.2 迭代(栈，深度优先搜索)

本迭代代码通过栈实现了对解空间树的深度优先搜索。

def numTilePossibilities(tiles): result = [] stack = [(tiles, '')] while stack: tiles, prefix = stack.pop() result.append(prefix) for i in sorted(set(tiles), reverse=True): stack.append((tiles.replace(i, '', 1), prefix+i)) return result[1:] print(numTilePossibilities('AAB')) print(numTilePossibilities('AABC')) 

实验结果：
[‘A’, ‘AA’, ‘AAB’, ‘AB’, ‘ABA’, ‘B’, ‘BA’, ‘BAA’]
[‘A’, ‘AA’, ‘AAB’, ‘AABC’, ‘AAC’, ‘AACB’, ‘AB’, ‘ABA’, ‘ABAC’, ‘ABC’, ‘ABCA’, ‘AC’, ‘ACA’, ‘ACAB’, ‘ACB’, ‘ACBA’, ‘B’, ‘BA’, ‘BAA’, ‘BAAC’, ‘BAC’, ‘BACA’, ‘BC’, ‘BCA’, ‘BCAA’, ‘C’, ‘CA’, ‘CAA’, ‘CAAB’, ‘CAB’, ‘CABA’, ‘CB’, ‘CBA’, ‘CBAA’]

3.3 迭代(栈)

def numTilePossibilities(tiles): result = [] stack = [(tiles, '')] while stack: tiles, prefix = stack.pop() for i in sorted(set(tiles)): result.append(prefix+i) stack.append((tiles.replace(i, '', 1), prefix+i)) return result print(numTilePossibilities('AAB')) print(numTilePossibilities('AABC')) 

实验结果：
[‘A’, ‘B’, ‘BA’, ‘BAA’, ‘AA’, ‘AB’, ‘ABA’, ‘AAB’]
[‘A’, ‘B’, ‘C’, ‘CA’, ‘CB’, ‘CBA’, ‘CBAA’, ‘CAA’, ‘CAB’, ‘CABA’, ‘CAAB’, ‘BA’, ‘BC’, ‘BCA’, ‘BCAA’, ‘BAA’, ‘BAC’, ‘BACA’, ‘BAAC’, ‘AA’, ‘AB’, ‘AC’, ‘ACA’, ‘ACB’, ‘ACBA’, ‘ACAB’, ‘ABA’, ‘ABC’, ‘ABCA’, ‘ABAC’, ‘AAB’, ‘AAC’, ‘AACB’, ‘AABC’]

3.4 迭代(队列)

本迭代代码通过队列实现了对解空间树的广度优先搜索(breadth first search, bfs)。

def numTilePossibilities(tiles): result = [] queue = [(tiles, '')] while queue: tiles, prefix = queue.pop(0) for i in sorted(set(tiles)): result.append(prefix+i) queue.append((tiles.replace(i, '', 1), prefix+i)) return result print(numTilePossibilities('AAB')) print(numTilePossibilities('AABC')) 

实验结果：
[‘A’, ‘B’, ‘AA’, ‘AB’, ‘BA’, ‘AAB’, ‘ABA’, ‘BAA’]
[‘A’, ‘B’, ‘C’, ‘AA’, ‘AB’, ‘AC’, ‘BA’, ‘BC’, ‘CA’, ‘CB’, ‘AAB’, ‘AAC’, ‘ABA’, ‘ABC’, ‘ACA’, ‘ACB’, ‘BAA’, ‘BAC’, ‘BCA’, ‘CAA’, ‘CAB’, ‘CBA’, ‘AABC’, ‘AACB’, ‘ABAC’, ‘ABCA’, ‘ACAB’, ‘ACBA’, ‘BAAC’, ‘BACA’, ‘BCAA’, ‘CAAB’, ‘CABA’, ‘CBAA’]

本文地址：https://blog.csdn.net/weixin_43918780/article/details/108256263