[搜狗]找一个字符串中包含全部出现字符的最小字串


就如题目所说,一个字符串中含有n个字符,其中有m个不同的字符,n>>m,用最少的时间和空间找到包含所有这m个字符的最短的字串,不考虑特殊字符,只考虑字母数字即可。
例如:
abccbaddac, 返回:cbad
aabcadbbbcca,返回:bcad

题目不简单,求大神解法!
已邀请:

leerain

赞同来自: 不二熊

utf-8

def minsub(str,m):
    substart = 0
    subend = m
    minisub = str
    while True:
        tempsub = str[substart:subend]
        tempsubs = set(tempsub)
        while len(tempsubs) < m:
            subend += 1
            if subend > len(str):
                break
            tempsub = str[substart:subend]
            tempsubs = set(tempsub) 
            
        if len(tempsub) < len(minisub):         
            minisub = tempsub
        if len(minisub) == m:
            break
        substart = subend - m
        subend = substart + m
        if subend == len(str):
            break
    print minisub
    
if __name__ == "__main__":
    str = 'abc6cbdb6add6ac'
    m = 5
    minsub(str, m)
        
    


我觉得思路还是很清晰,简单的。
首先,给定一个字符串,长度为n。至于,有多少不同的字符(包括字母大小写,数字),我用的是python,对原字符串set一下,去掉重复的元素,就得到不同的字符,长度为m。
开始遍历寻找最短子串:
1,采用滑动窗口的方式,第一次的窗口长度为m,用两个参数分别指向窗口头和窗口尾,如果这个窗口里不包含全部的字符,那么窗口尾参数+1,让窗口变长,一个一个的往原窗口中加字符,直到包含全部字符。
2,得到第一个包含全部字符的子串后,调整指向窗口头和窗口尾的参数,假设上一次得到全部字符的窗口长度为L,那么就从上一次窗口中的第L-m个元素开始,也就是这一次窗口头参数指向这个元素,窗口大小为m开始新一轮寻找,窗口变化同上。
3,重复第二步,直到找到一个长度刚好为m的子串就结束寻找,或者,直到窗口尾参数指向原字符的最后一个字符,而且窗口大小刚好为m也结束查找,比较每一次包含全部字符的子串长度,保留短的。
遍历一次就可以找到。

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~