Python:每日一题 337
今天的题目:给定一个字符串,返回字符串的非空不同子串的个数。
示例 1:
输入:"abc"
输出:7
解释:7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。
示例 2:
输入:"aba"
输出:6
解释:6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。
示例 3:
输入:"aaa"
输出:3
解释:3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。
{:10_298:}欢迎大家一起答题!{:10_298:} 本帖最后由 TJBEST 于 2020-2-26 15:34 编辑
先写一个可能会超时的,递归的,后面再想想别的方法优化
def fun337(string):#数学计算法
def inner(index):
if len(set(string)) == M - index:
return 2**(M - index - 1)
else:
result = 1
for eachNum in dictionary:
for inner_index in dictionary:
if inner_index > index:
if inner_index in resultDict:
result += resultDict
else:
temp = inner(inner_index)
result += temp
resultDict=temp
break
return result
dictionary = {}
resultDict = {}
M = len(string)
for index in range(0,M):
try:
dictionary].append(index)
except Exception:
dictionary] =
result = 0
if len(set(string)) == M:
result += 2**M - 1
else:
for eachNum in dictionary:
if dictionary in resultDict:
result += resultDict]
else:
temp = inner(dictionary)
result += temp
resultDict]=temp
return result 给定的这个字符串能不能为空? fan1993423 发表于 2020-2-25 16:32
给定的这个字符串能不能为空?
保证字符串不为空。 哦,我想问下,比如abac 是不是ab,aa,,ac,ba,bc,ac,aba,abc,bac都是,但cab这种倒过来的不是? fan1993423 发表于 2020-2-25 16:38
哦,我想问下,比如abac 是不是ab,aa,,ac,ba,bc,ac,aba,abc,bac都是,但cab这种倒过来的不是?
是的。 def f337(x):
s=set(' ')
for a in x:
s|={e+a for e in s}
return len(s)-1
写个无脑版本,超时先不管了 塔利班 发表于 2020-2-25 16:42
写个无脑版本,超时先不管了
{:10_250:}{:10_250:}
输入 "pcrdhwdxmqdznbenhwjsenjhvulyve" 超出内存限制 嗯,排列组合题,先写个效率偏低的
from itertools import combinations
def fun337(s):
result=0
if len(s)==1:return 1
elif len(s)==2:return 3 if len(set(s))==2 else 2
for i in range(2,len(s)):result+=len(set(combinations(s,i)))
result+=len(set(s))+1
return result fan1993423 发表于 2020-2-25 16:56
嗯,排列组合题,先写个效率偏低的
输入 "pcrdhwdxmqdznbenhwjsenjhvulyve" 超出内存限制 来个比较蠢的方法
def f337(s):
rs, l = [], len(s)
for i in range(l):
for j in range(i+1, l+1):
if s not in rs:
rs.append(s)
if s not in rs:
rs.append(s)
return len(rs) kinkon 发表于 2020-2-25 17:09
来个比较蠢的方法
解答错误
输入:"bebb"
输出:8
预期结果:9 zltzlt 发表于 2020-2-25 17:10
解答错误
输入:"bebb"
能不能抽空列出9个包括哪些? kinkon 发表于 2020-2-25 17:20
能不能抽空列出9个包括哪些?
e, bbb, bebb, beb, bb, b, eb, ebb, be zltzlt 发表于 2020-2-25 16:41
是的。
abc和bac也是一样的吧?这应该是找组合,不是找排列。 jeezy 发表于 2020-2-25 17:52
abc和bac也是一样的吧?这应该是找组合,不是找排列。
是的 zltzlt 发表于 2020-2-25 17:23
e, bbb, bebb, beb, bb, b, eb, ebb, be
看看还有没有问题
def f337(s):
rs, l = [], len(s)
for i in range(l):
for j in range(i+1, l+1):
if s not in rs:
rs.append(s)
if s not in rs:
rs.append(s)
return len(rs)
print(f337("bebb"))
print(f337("abc"))
def f337(s):
rs, l = [], len(s)
for i in range(l):
for j in range(i+1, l+1):
if s not in rs:
rs.append(s)
if s not in rs:
rs.append(s)
return len(rs)
print(f337("bebb"))
print(f337("abc"))
print(f337("aba"))
print(f337("aba"))
print(f337("aaa")) ef f337(s):
rs, l = [], len(s)
for i in range(l):
for j in range(i+1, l+1):
if s not in rs:
rs.append(s)
if s not in rs:
rs.append(s)
return len(rs)
print(f337("abc"))
print(f337("aba"))
print(f337("aba"))
print(f337("aaa")) def fc337(string):
s=set()
for i in range(1,2**len(string)):
l=str(bin(i))
if len(l)<len(string):
l='0'*(len(string)-len(l))+l
s.add(''.join( for n,e in enumerate(l) if e=='1']))
print(len(s))
说白了就是找子集,幸好以前做过找子集,