[LeetCode]题解（python）：030-Substring with Concatenation of All Words
题目来源
https://leetcode.com/problems/substring-with-concatenation-of-all-words/
You are given a string,s, and a list of words,words, that are all of the same length.
Find all starting indices of substring(s) insthat is a concatenation of each word inwordsexactly once and without any intervening characters.
题意分析
Input：a str and a list
Output:a list recorded the indices
Conditions：输入一个字符串s和一连串的长度相同的字符串数组words，找出仅由所有的words组成的s的子字符串起始位置。words内的元素可能重复，但是每个元素都需要出现（如有两个‘good’元素，那么’good‘就需要出现两次）
examples:
s:"barfoothefoobarman"
words:["foo", "bar"]
You should return the indices:[0,9].
题目思路
- 首先将words存为一个dic（dictiionary（字典））（出现一次value为1，出现两次value为2，以此类推）
- 遍历每一个可能的str（长度等于len（words）*len（words[0]））
- 对每一个str，用一个新的字典d来存储已经出现的word，用python的分片来访问每一个str里面的word，用计数器count计数相等的word
- 条件检验：如果元素不在dic，直接break取下一个可能的str；如果元素在dic，但是不在d，直接将新元素加入到d，value取为1，count加1；如果元素在dic，同时也在d，看此时d中的value是否小于dic中的value，小于则value加1，count加1，否则此字串不满足条件，舍弃取下一条str
- 每一次对一个str处理后，d要清空，count要置为0
- 注意事项：d.get(each_str, -1) != -1的速度不如 each_str in d
AC代码（Python）
1 _author_ = "YE" 2 # -*- coding:utf-8 -*- 3 # SH……把d.get(each_str, -1) == -1类似的判断改为 each_str not in d 就AC了……说明后者效率高呀 4 def findSubstring(s, words): 5 """ 6 :type s: str 7 :type words: List[str] 8 :rtype: List[int] 9 """ 10 import math 11 rtype = [] 12 dic = {} 13 14 len_word = len(words) 15 if len_word == 0: 16 return rtype 17 #print('len of words:%s' % len_word) 18 19 len_each_word = len(words[0]) 20 #print('len of each word:%s' % len_each_word) 21 22 all_len = len_word * len_each_word 23 #print("all len:", all_len) 24 25 for x in words: 26 if x in dic: 27 dic[x] = dic[x] + 1 28 else: 29 dic[x] = 1 30 31 #print('dictionary:') 32 #print(dic) 33 34 #print(dic.get('arf',-1) == -1) 35 36 len_s = len(s) 37 #print('the len of the str s', len_s) 38 39 if len_s < all_len: 40 return rtype 41 42 #print('From loop') 43 44 for i in range(len_s - all_len + 1): 45 str = s[i:i+all_len] 46 count = 0 47 d = {} 48 for j in range(len_word): 49 each_str = str[j * len_each_word:(j + 1) * len_each_word] 50 if each_str not in dic: 51 count = 0 52 break 53 elif each_str in d: 54 if d[each_str] == dic[each_str]: 55 count = 0 56 break 57 else: 58 d[each_str] = d[each_str] + 1 59 count = count + 1 60 continue 61 else: 62 d[each_str] = 1 63 count = count + 1 64 if count == len_word: 65 rtype.append(i) 66 count = 0 67 #print(rtype)View Code 优质内容筛选与推荐>>
1、将博客搬至CSDN
2、考完了！考完了！
3、找出不在给定数组中的最小正整数
4、实验1.2 C语言上机入门 二
5、共迎海量数据库管理挑战 中韩数据库专家对话北京