首页 > 其他 > 详细

给定一个字符串s和一个由多个等长字符串组成的列表words,输出列表中的字符串组成的整体在s中的所有可能的位置

时间:2019-04-11 13:40:42      阅读:265      评论:0      收藏:0      [点我收藏+]

示例:

输入:s = "abcmmedfrgaqwedfrmme"   words=["mme","dfr"]

输出:[3,14]

Python解决方案:

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        if not words:
            return []
        w_len = len(words[0])       
        all_len = w_len*len(words)
        
        out = []
        word_count = collections.Counter(words)
        
        for i in range(len(s)-all_len+1):
            sub_i = s[i:i+w_len]
            if sub_i in word_count:
                j = i + w_len
                wc = word_count.copy()
                wc[sub_i] -= 1
                while j <= all_len + i-w_len:
                    sub = s[j:j+w_len]
                    if sub in wc and wc[sub]:
                        wc[sub] -= 1
                        j += w_len
                        pre = sub
                    else:
                        break
                if not sum(wc.values()):
                    out.append(i)                  
        return out

 

给定一个字符串s和一个由多个等长字符串组成的列表words,输出列表中的字符串组成的整体在s中的所有可能的位置

原文:https://www.cnblogs.com/wenqinchao/p/10688959.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!