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

zltzlt

今天的题目：

给定字符串 s 和字符串数组 words，求 words 中是 s 的子串的字符串个数。

示例：

输入：s = "abcde", words = ["a", "bb", "acd", "ace"]
输出：3
解释：有三个是 s 的子序列的单词："a"，"acd"，和 "ace" 。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

阴阳神万物主

2020-4-5 07:11:30

难度评级：简单
要素分析：字符串 查找
代码：

1. def solve(s:str,words:list)->int:
   
2.     res = 0
   
3.     for word in words:
   
4.         i = 0
   
5.         for each in word:
   
6.             i = s.find(each,i)+1
   
7.             if not i:
   
8.                 break
   
9.         else:
   
10.             res += 1
    
11.     return res
    
12. 
    
13. if __name__ == '__main__':
    
14.     print('示例 输出：',solve('abcde',['a','bb','acd','ace']))
    

复制代码

忐忑.png
不知道超时否。

跳转到最佳答案楼层

March2615

s里面是可以重复的？
比如输入：s=“abcdea”， words = ["cda"]
这时输出是1？

1. def daily368(s: str, words: list) -> int:
   
2.     ans = 0
   
3.     word_list = {}
   
4.     for word in words:
   
5.         if word[0] not in word_list.keys():  # 需要一个key为26个字母、value为列表储存后续单词的字典
   
6.             word_list[word[0]] = []
   
7.         word_list[word[0]].append(word[1:])
   
8.     for ch in s:
   
9.         if ch in word_list:
   
10.             ch_word = word_list[ch]  # ch_word是以ch为开头的单词
    
11.             del word_list[ch]
    
12.             for word in ch_word:
    
13.                 if word == '':
    
14.                     ans += 1
    
15.                 else:
    
16.                     if word[0] not in word_list.keys():
    
17.                         word_list[word[0]] = []
    
18.                     word_list[word[0]].append(word[1:])
    
19.     return ans

复制代码

就按照我的想法来了
思路是把words按照首字母分类，首字母在s里面出现后，删除首字母，将剩余的单词重新分类，遍历一次s就可以得到答案

BngThea

1. def fun368(s,words):
   
2.     cnt = 0
   
3.     for each in words:
   
4.         t = s[:]
   
5.         for letter in each:            
   
6.             if letter not in t:
   
7.                 break
   
8.             else:
   
9.                 t = t.replace(letter,'')
   
10.         else:            
    
11.             cnt += 1
    
12.     return cnt

复制代码

TJBEST

先来一个效率低的

1. def fun368(s,words):
   
2.     def isSub(sub):
   
3.         temp = s
   
4.         for each in sub:
   
5.             try:
   
6.                 position = temp.index(each)
   
7.                 temp = temp[(position+1):]
   
8.             except Exception:
   
9.                 return False
   
10.         return True
    
11.     result = 0
    
12.     for eachword in words:
    
13.         if isSub(eachword):
    
14.             result += 1
    
15.     return result

复制代码

l0stparadise

1. def f368(s,words):
   
2.     def find_str(s,str1):
   
3.         index=-1
   
4.         for i in str1:
   
5.             index = s.find(i,index+1,len(s))
   
6.             if index == -1:
   
7.                 return False
   
8.         else:
   
9.             return True
   
10.     count = 0
    
11.     for j in words:
    
12.         if find_str(s,j):
    
13.             count += 1
    
14.     return count

复制代码

ouyunfu

1. import re
   
2. def f368(s,words):
   
3.     count=0
   
4.     for i in words:
   
5.         s1 = s[:]
   
6.         for m in i:
   
7.             if m not in s1:
   
8.                 break
   
9.             else: s1=s1.replace(m,'')
   
10.         else:
    
11.             a=[max([i.start() for i in re.finditer(j,s)]) for j in i]
    
12.             if sorted(a)==a:
    
13.                 count+=1
    
14.     return count

复制代码

TJBEST

@zltzlt 我个人理解 子串的元素顺序得和s的一致吧 比如'asd'的子串不包括'sa'但是包含'ad'？

kinkon

看例子感觉有顺序要求啊

1. def f368(s, words):
   
2.     out = 0
   
3.     for w in words:
   
4.         left = 0
   
5.         bg = True
   
6.         for x in w:               
   
7.             tmp = s[left:].find(x)
   
8.             if tmp == -1:
   
9.                 bg = False
   
10.                 break
    
11.             else:
    
12.                 left = tmp + 1
    
13.         if bg:
    
14.             out += 1
    
15.     return out

复制代码

再来一个，试试哪个快

1. from collections import Counter
   
2. def f368(s, words):
   
3.     s_cout = Counter(s)
   
4.     out = 0
   
5.     for w in words:
   
6.         w_cout = Counter(w)
   
7.         if all(s_cout[x] >= w_cout[x] for x in w_cout):
   
8.             if list((s_cout + w_cout - s_cout).elements()) == list(w):              
   
9.                 out += 1
   
10.     return out

复制代码

chen971130

1. def a368(s,words):
   
2.     s,count = list(s),0
   
3.     for i in words:
   
4.         k = 0
   
5.         for j in s:
   
6.             if j == list(i)[k]:
   
7.                 k += 1
   
8.             if k == len(list(i)):
   
9.                 count += 1
   
10.                 break
    
11.     print(count)
    
12. a368('abcde',['a','bb','acd','ace'])

复制代码

jdzzj

1. def fun368(s,words):
   
2. 
   
3.     count = 0
   
4. 
   
5.     def issubseq(s, t):
   
6. 
   
7.         index = 0
   
8.         for i in s:
   
9.             index = t.find(i, index)
   
10.             if index < 0:
    
11.                 return False
    
12.             index += 1
    
13. 
    
14.         return True
    
15. 
    
16.     for j in words:
    
17. 
    
18.         if issubseq(j,s):
    
19.             count += 1
    
20.         else:
    
21.             continue
    
22. 
    
23.     return count

复制代码

ouyunfu

1. def f368(s:str,words:list)->int:
   
2.     count=0
   
3.     for i in words:
   
4.         m = 0
   
5.         for j in s:
   
6.             if j == i[m]:
   
7.                 m += 1
   
8.             if m == len(i):
   
9.                 count += 1
   
10.                 break
    
11.     return count

复制代码

fan1993423

adc是不是acde的子序列

whosyourdaddy

def func368(s,words):
    temp = set(s)
    dicts = {}
    count = 0
    for each in temp:
        dicts[each] = s.count(each)
    for i in range(len(words)):
        temp = set(words[i])
        for j in temp:
            if words[i].count(j) > dicts[j]:
                count -= 1
                break
        count += 1
    return count

kinkon

fan1993423 发表于 2020-4-4 23:41
adc是不是acde的子序列

应该不是

阴阳神万物主

难度评级：简单
要素分析：字符串 查找
代码：

1. def solve(s:str,words:list)->int:
   
2.     res = 0
   
3.     for word in words:
   
4.         i = 0
   
5.         for each in word:
   
6.             i = s.find(each,i)+1
   
7.             if not i:
   
8.                 break
   
9.         else:
   
10.             res += 1
    
11.     return res
    
12. 
    
13. if __name__ == '__main__':
    
14.     print('示例 输出：',solve('abcde',['a','bb','acd','ace']))
    

复制代码

忐忑.png
不知道超时否。

永恒的蓝色梦想

占楼

旅途Z

1. def find_sub_str(string, str_list):
   
2.     str_num = 0
   
3. 
   
4.     def is_substring(str1, str2):
   
5.         j = 0
   
6.         for i in range(len(str2)):
   
7.             find_position = str1.find(str2[i], j)
   
8.             if find_position != -1:
   
9.                 j = find_position + 1
   
10.             else:
    
11.                 return False
    
12.         else:
    
13.             return True
    
14.     for i in range(len(str_list)):
    
15.         if is_substring(string, str_list[i]):
    
16.             str_num += 1
    
17.     return str_num

复制代码

风魔孤行者

1. def f(s,words):
   
2.     dict1 = {}
   
3.     for each in s:
   
4.         if each not in dict1.keys():
   
5.             dict1[each] = 0
   
6.         dict1[each] += 1
   
7.     def f1(dict1,s):
   
8.         for each in s:
   
9.             if s.count(each) <= dict1[each]:
   
10.                 s.replace('each','')
    
11.             else:
    
12.                 return False
    
13.         return True
    
14.     n = 0
    
15.     for each in words:
    
16.         if f1(dict1,each):
    
17.             n += 1
    
18.     return n

复制代码

山岂乎不在高

def f(s,w):
    for i in w:
        a=s.find(i)
        if a==-1:
            return 0
        s=s[a+1:]
    return 1

s = "abcde"
words = ["a", "bb", "acd", "ace"]
  
print(sum(f(s,w) for w in words))

lucky邪神

1. import re
   
2. 
   
3. resultnum=0
   
4. 
   
5. 
   
6. def just(s,word): #判断word是否是s的子字符串，是返回True,否返回False
   
7.     length=len(word)
   
8.     for i in range(length):
   
9.        rflag=re.search(word[i],s)
   
10.        if rflag==None:
    
11.            return False
    
12.            
    
13.        t=rflag.span()
    
14.        index=t[1]
    
15.        s=s[index:]
    
16.       
    
17.     return True
    
18. 
    
19. if __name__=='__main__':
    
20.     enter=input("请输入检测的字符串，以‘，’隔开：")
    
21.     s=input("请输入给定的字符串")
    
22.     words=[word for word in enter.split(',')]
    
23.     for each in words:
    
24.         if just(s,each)==True:
    
25.             resultnum+=1
    
26.             print(each)
    
27. 
    
28.     print (resultnum)
    

复制代码