# 描述

``````给你一个字符串?text，你需要使用 text 中的字母来拼凑尽可能多的单词?"balloon"（气球）。

?

# 解答

bucket 数组，（或者用map/py 字典实现更好）

## cpp

todo watch

``````int maxNumberOfBalloons(char * text){
int* hashSet=(int*)malloc(sizeof(int)*128);
memset(hashSet,0,sizeof(int)*128);
int textLength = 0;
while(text[textLength]){
hashSet[text[textLength]]++;
textLength++;
}

int wordQty = textLength;
wordQty = (wordQty>hashSet['a'])?hashSet['a']:wordQty;
wordQty = (wordQty>hashSet['b'])?hashSet['b']:wordQty;
wordQty = (wordQty>hashSet['n'])?hashSet['n']:wordQty;
wordQty = (wordQty>(hashSet['o']>>1))?(hashSet['o']>>1):wordQty;
wordQty = (wordQty>(hashSet['l']>>1))?(hashSet['l']>>1):wordQty;

free(hashSet);
return wordQty;
}``````

## py

``````class Solution:
def maxNumberOfBalloons(self, text: str) -> int:
mydict = {}
tgt = ['b','a','l','o','n']
for i in tgt:
mydict[i] = 0
for c in text:
if c in tgt:
mydict[c] = mydict[c] + 1 # # 这里是否需要初始化mydict的key value（=0）呢？
counter = mydict['a']
for k in mydict:
tmp1 = mydict[k]
if k == 'l' or k == 'o':
tmp = tmp1 // 2
if tmp < counter:
counter = tmp
else:
if tmp1 < counter:
counter = tmp1
return counter
'''执行用时 :
44 ms
, 在所有 Python3 提交中击败了
37.20%

13.5 MB
, 在所有 Python3 提交中击败了
35.66%

## improved py

``````class Solution:
def maxNumberOfBalloons(self, text: str) -> int:
d = collections.Counter(text)
return min(d['b'], d['a'], d['l'] // 2, d['o'] // 2, d['n'])``````

# ? 784. 字母大小写全排列

https://leetcode-cn.com/problems/letter-case-permutation

# 描述

``````给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

S 的长度不超过12。
S 仅由数字和字母组成。

# 解答

## c: `backTrace` !! powerful: backTrace; rev me; todo

``````//C语言实现，递归回溯 todo

#define MAX_SIZE 10240//tt do we really need so big space for g_re??
#define STR_SIZE 15

struct StrRecord {
char str[STR_SIZE];
int pos;
};

struct StrRecord g_str;
int g_num = 0;
char **g_re;//tt why double ptr here?: a ptr point other bunch of ptrs;

void backTrace(char *S, int len, int start)
{
//tt when the recursive goto the end (of the S)
//tt we can add the recursive result to the g_re.
if (g_str.pos == len) {
g_re[g_num++] = strdup(g_str.str);
}
//tt otherwise: we start from `start` to traverse
//tt all the left char in S(using S[i]);
//tt to set each alpha char to lower / upper
//tt each alpha has two possible output: lower / upper
for (int i = start; i < len; i++) {
if (isalpha(S[i])) {
int tmpLower = tolower(S[i]);
g_str.str[g_str.pos++] = tmpLower;
//tt backTrace always go to next
backTrace(S, len, i + 1);
//tt here we see: `g_str.pos--`
//tt which jst represent: BACKTrace
g_str.str[g_str.pos--];
int tmpUpper = toupper(S[i]);
g_str.str[g_str.pos++] = tmpUpper;
} else {
//tt when it's not alpha(aka num)
//tt all we need to do is give num to g_str.str
g_str.str[g_str.pos++] = S[i];
}
//tt watch this: two lines: are also the keys of backTrace!!
backTrace(S, len, i + 1);
g_str.str[g_str.pos--];
}
}

char **letterCasePermutation(char *S, int *returnSize)
{
g_re = malloc(sizeof(char *) * MAX_SIZE);
g_num = 0;
memset(&g_str, 0, sizeof(g_str));
int len = strlen(S);
backTrace(S, len, 0);
*returnSize = g_num;
return g_re;
}
``````

## py todo watch me; three me

DFS 回溯 看到题目要求组合或者集合，马上想到可以用回溯法：回溯法本来是说对于每个元素都先考虑放它的情况，再考虑不放它的情况；放在这道题的背景里就是，对于每个字母，先考虑放它，再考虑放它的另一种大小写形式。

``````class Solution:
def letterCasePermutation(self, S: str) -> List[str]:
ret = list()
l = len(S)
if l == 0:
return ['']# is the same as [""]? seems yes
def dfs(start, tmp):
if (start >= l or len(tmp) >= l):
ret.append(tmp)
return
if S[start].isdigit():
dfs(start + 1, tmp + S[start])
elif S[start].islower():
dfs(start + 1, tmp + S[start])
dfs(start + 1, tmp + S[start].upper())
elif S[start].isupper():
dfs(start + 1, tmp + S[start])
dfs(start + 1, tmp + S[start].lower())

dfs(0, "")
return ret
'''

116 ms
, 在所有 Python3 提交中击败了
17.12%

14.8 MB
, 在所有 Python3 提交中击败了
17.43%

'''
``````

todo watch ??

### BFS 除了用DFS回溯实现，我们也可以用BFS来解题

``````class Solution(object):
def letterCasePermutation(self, S):
"""
:type S: str
:rtype: List[str]
"""
import copy
res = [""]

for i, x in enumerate(S):
# if len(res) == 0:
#     res.append(x)
if x.isdigit():#数字就每个答案都加进去
for index, item in enumerate(res):
res[index] += (x)
elif x.isupper():#字母就每个答案先放自己再放对立面
temp = list()
for index, item in enumerate(res):
# print item
temp.append(item + (x))
temp.append(item + (x.lower()))
res = copy.deepcopy(temp[:])
elif x.islower():
temp = list()
for index, item in enumerate(res):
temp.append(item + (x))
temp.append(item + (x.upper()))
res = copy.deepcopy(temp[:])
# print temp
return res``````

### BitMap

Bitmap法，字符串S的长度为l， 则总共会有 2** l种结果，换成二进制就是0 ~ 2 **l - 1个数，

``````class Solution(object):
def letterCasePermutation(self, S):
l = len(S)
n = 2 ** l
res = list()
if l == 0:
res.append("")
for i in range(0, n): #得到0 ~ 2 ** l 的每个数
temp = ""

for j in range(0, l):
if ((2 ** j) &i) == 0:#当前位是0， 放小写
temp += S[j].lower()
else: #放大写
temp += S[j].upper()
if temp not in res:
res.append(temp)
return res
``````

lc 0227

(0)
(0)