[已解决]Python：每日一题 337

zltzlt

今天的题目：

给定一个字符串，返回字符串的非空不同子串的个数。

示例 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"。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

TJBEST

2020-2-25 15:48:32

先写一个可能会超时的，递归的，后面再想想别的方法优化

1. def fun337(string):#数学计算法
   
2.     def inner(index):
   
3.         if len(set(string[index:])) == M - index:
   
4.             return 2**(M - index - 1)
   
5.         else:
   
6.             result = 1
   
7.             for eachNum in dictionary:
   
8.                 for inner_index in dictionary[eachNum]:
   
9.                     if inner_index > index:
   
10.                         if inner_index in resultDict:
    
11.                             result += resultDict[inner_index]
    
12.                         else:
    
13.                             temp = inner(inner_index)
    
14.                             result += temp
    
15.                             resultDict[inner_index]=temp
    
16.                         break
    
17.             return result
    
18.         
    
19.                                  
    
20.     dictionary = {}
    
21.     resultDict = {}
    
22.     M = len(string)
    
23.     for index in range(0,M):
    
24.         try:
    
25.             dictionary[string[index]].append(index)
    
26.         except Exception:
    
27.             dictionary[string[index]] = [index]
    
28.     result = 0
    
29.     if len(set(string)) == M:
    
30.         result += 2**M - 1
    
31.     else:
    
32.         for eachNum in dictionary:
    
33.             if dictionary[eachNum][0] in resultDict:
    
34.                 result += resultDict[dictionary[eachNum][0]]
    
35.             else:
    
36.                 temp = inner(dictionary[eachNum][0])
    
37.                 result += temp
    
38.                 resultDict[dictionary[eachNum][0]]=temp
    
39.     return result

复制代码

跳转到最佳答案楼层

TJBEST

先写一个可能会超时的，递归的，后面再想想别的方法优化

1. def fun337(string):#数学计算法
   
2.     def inner(index):
   
3.         if len(set(string[index:])) == M - index:
   
4.             return 2**(M - index - 1)
   
5.         else:
   
6.             result = 1
   
7.             for eachNum in dictionary:
   
8.                 for inner_index in dictionary[eachNum]:
   
9.                     if inner_index > index:
   
10.                         if inner_index in resultDict:
    
11.                             result += resultDict[inner_index]
    
12.                         else:
    
13.                             temp = inner(inner_index)
    
14.                             result += temp
    
15.                             resultDict[inner_index]=temp
    
16.                         break
    
17.             return result
    
18.         
    
19.                                  
    
20.     dictionary = {}
    
21.     resultDict = {}
    
22.     M = len(string)
    
23.     for index in range(0,M):
    
24.         try:
    
25.             dictionary[string[index]].append(index)
    
26.         except Exception:
    
27.             dictionary[string[index]] = [index]
    
28.     result = 0
    
29.     if len(set(string)) == M:
    
30.         result += 2**M - 1
    
31.     else:
    
32.         for eachNum in dictionary:
    
33.             if dictionary[eachNum][0] in resultDict:
    
34.                 result += resultDict[dictionary[eachNum][0]]
    
35.             else:
    
36.                 temp = inner(dictionary[eachNum][0])
    
37.                 result += temp
    
38.                 resultDict[dictionary[eachNum][0]]=temp
    
39.     return result

复制代码

fan1993423

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

zltzlt

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

保证字符串不为空。

fan1993423

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

zltzlt

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

是的。

塔利班

1. def f337(x):
   
2.     s=set(' ')
   
3.     for a in x:
   
4.         s|={e+a for e in s}
   
5.     return len(s)-1

复制代码

写个无脑版本，超时先不管了

zltzlt

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

输入 "pcrdhwdxmqdznbenhwjsenjhvulyve" 超出内存限制

fan1993423

嗯，排列组合题，先写个效率偏低的

1. from itertools import combinations
   
2. def fun337(s):
   
3.     result=0
   
4.     if len(s)==1:return 1
   
5.     elif len(s)==2:return 3 if len(set(s))==2 else 2
   
6.     for i in range(2,len(s)):result+=len(set(combinations(s,i)))
   
7.     result+=len(set(s))+1
   
8.     return result

复制代码

zltzlt

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

输入 "pcrdhwdxmqdznbenhwjsenjhvulyve" 超出内存限制

kinkon

来个比较蠢的方法

1. def f337(s):
   
2.     rs, l = [], len(s)
   
3.     for i in range(l):
   
4.         for j in range(i+1, l+1):
   
5.             if s[i:j] not in rs:      
   
6.                 rs.append(s[i:j])
   
7.             if s[i::j] not in rs:      
   
8.                 rs.append(s[i::j])
   
9.     return len(rs)

复制代码

zltzlt

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

解答错误

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

kinkon

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

输入："bebb"

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

zltzlt

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

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

jeezy

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

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

zltzlt

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

是的

kinkon

zltzlt 发表于 2020-2-25 17:23
e, bbb, bebb, beb, bb, b, eb, ebb, be

看看还有没有问题

1. def f337(s):
   
2.     rs, l = [], len(s)
   
3.     for i in range(l):
   
4.         for j in range(i+1, l+1):
   
5.             if s[i:j] not in rs:      
   
6.                 rs.append(s[i:j])
   
7.             if s[i::j] not in rs:      
   
8.                 rs.append(s[i::j+i])
   
9.     return len(rs)
   
10. print(f337("bebb"))
    
11. print(f337("abc"))   
    

复制代码

python/print

def f337(s):
    rs, l = [], len(s)
    for i in range(l):
        for j in range(i+1, l+1):
            if s[i:j] not in rs:      
                rs.append(s[i:j])
            if s[i::j] not in rs:      
                rs.append(s[i::j+i])
    return len(rs)
print(f337("bebb"))
print(f337("abc"))   
print(f337("aba"))
print(f337("aba"))
print(f337("aaa"))

python/print

ef f337(s):
    rs, l = [], len(s)
    for i in range(l):
        for j in range(i+1, l+1):
            if s[i:j] not in rs:      
                rs.append(s[i:j])
            if s[i::j] not in rs:      
                rs.append(s[i::j+i])
    return len(rs)
print(f337("abc"))   
print(f337("aba"))
print(f337("aba"))
print(f337("aaa"))

拉了盏灯

1. def fc337(string):
   
2.         s=set()
   
3.         for i in range(1,2**len(string)):
   
4.                 l=str(bin(i))[2:]
   
5.                 if len(l)<len(string):
   
6.                         l='0'*(len(string)-len(l))+l
   
7.                 s.add(''.join([string[n] for n,e in enumerate(l) if e=='1']))
   
8.         print(len(s))

复制代码

说白了就是找子集，幸好以前做过找子集，