题目
小红定义一个字符串的权值为:字符串长度乘以字符串的字母种类数量。例如,"abacb"的价值为5*3=15。
小红拿到了一个字符串,她准备将该字符串切分成𝑘个子串(将这𝑘个子串按顺序拼在一起即可得到原串)。小红希望切分后这𝑘个子串的最大权值尽可能小。你能帮帮小红吗?你不需要给出一个方案,只需要返回最终这𝑘个子串的最大权值即可。
字符串仅包含小写字母,且长度不超过500000。𝑘k为不超过字符串长度的正整数。
分析
通过回溯法列出所有可能的结果,再将所有结果遍历计算权值,最后取出权值最小的结果。
Python代码
class Solution:
def getMaxValue(self, st: str, n: int) -> int:
k = len(st)
ans = []
path = ['']*n
long = [0]*n
def sums(arr): # 判断总长度是否符合要求
x = 0
for i in arr:
x += int(i)
return x
def dfs(level, s): # 回溯函数
if level == n and sums(long) == k: # 回溯取结果条件
ans.append(path.copy())
return
if level > n-1:
return
for i in range(1, len(s)+1):
path[level] = s[0:i]
long[level] = i
dfs(level+1, s.replace(s[0:i], '', 1))
def mi(arr): # 取出最小权值
minn = [0]*len(arr)
ma = 0
for i in range(len(arr)):
for j in arr[i]:
if ma < len(j)*len(set(j)):
ma = len(j)*len(set(j))
minn[i] = ma
return min(minn)
dfs(0, st)
return mi(ans)
ss = 'abacb'
k = 1
a = Solution()
result = a.getMaxValue(ss, k)
print(result)
总结
对于全排列问题,在未知数组长度,无法用for循环解决诗时,我们可以通过回溯法很好的解决该问题。回溯法本质就是从穷举的结果中找出符合要求的解,主要是利用了解递归过程解决了n次循环的问题,要很好的掌握回溯法了解递归过程很重要。