zltzlt 发表于 2020-2-25 15:48:31

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-25 15:48:32

本帖最后由 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:30

给定的这个字符串能不能为空?

zltzlt 发表于 2020-2-25 16:35:41

fan1993423 发表于 2020-2-25 16:32
给定的这个字符串能不能为空?

保证字符串不为空。

fan1993423 发表于 2020-2-25 16:38:54

哦,我想问下,比如abac 是不是ab,aa,,ac,ba,bc,ac,aba,abc,bac都是,但cab这种倒过来的不是?

zltzlt 发表于 2020-2-25 16:41:03

fan1993423 发表于 2020-2-25 16:38
哦,我想问下,比如abac 是不是ab,aa,,ac,ba,bc,ac,aba,abc,bac都是,但cab这种倒过来的不是?

是的。

塔利班 发表于 2020-2-25 16:42:29

def f337(x):
    s=set(' ')
    for a in x:
      s|={e+a for e in s}
    return len(s)-1
写个无脑版本,超时先不管了

zltzlt 发表于 2020-2-25 16:44:00

塔利班 发表于 2020-2-25 16:42
写个无脑版本,超时先不管了

{:10_250:}{:10_250:}

输入 "pcrdhwdxmqdznbenhwjsenjhvulyve" 超出内存限制

fan1993423 发表于 2020-2-25 16:56:42

嗯,排列组合题,先写个效率偏低的
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

zltzlt 发表于 2020-2-25 16:59:38

fan1993423 发表于 2020-2-25 16:56
嗯,排列组合题,先写个效率偏低的

输入 "pcrdhwdxmqdznbenhwjsenjhvulyve" 超出内存限制

kinkon 发表于 2020-2-25 17:09:57

来个比较蠢的方法
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)

zltzlt 发表于 2020-2-25 17:10:40

kinkon 发表于 2020-2-25 17:09
来个比较蠢的方法

解答错误

输入:"bebb"
输出:8
预期结果:9

kinkon 发表于 2020-2-25 17:20:40

zltzlt 发表于 2020-2-25 17:10
解答错误

输入:"bebb"


能不能抽空列出9个包括哪些?

zltzlt 发表于 2020-2-25 17:23:04

kinkon 发表于 2020-2-25 17:20
能不能抽空列出9个包括哪些?

e, bbb, bebb, beb, bb, b, eb, ebb, be

jeezy 发表于 2020-2-25 17:52:45

zltzlt 发表于 2020-2-25 16:41
是的。

abc和bac也是一样的吧?这应该是找组合,不是找排列。

zltzlt 发表于 2020-2-25 17:54:11

jeezy 发表于 2020-2-25 17:52
abc和bac也是一样的吧?这应该是找组合,不是找排列。

是的

kinkon 发表于 2020-2-25 18:19:19

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"))   

python/print 发表于 2020-2-25 18:53:23

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"))

python/print 发表于 2020-2-25 18:57:08

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"))

拉了盏灯 发表于 2020-2-25 18:57:21

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))
说白了就是找子集,幸好以前做过找子集,
页: [1] 2 3 4
查看完整版本: Python:每日一题 337