首页 > 试题广场 >

寻找最小子字符串

[编程题]寻找最小子字符串

热度指数：1840 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美和小团在玩一个游戏，小美任意给出一个大字符串str1以及一个独立的小字符串str2，小团需要从这个大字符串str1里找到包含独立小字符串str2中所有字符的最小子字符串str3；
例如，小美给出一个大字符串"meituan2019"和一个子字符串"i2t"，那么小团给出的答案就应该是"ituan2"；

需要注意：
1、str1中有可能没有完整包含str2所有字符的情况，此时返回""，即为空字符串；
2、str1不会为空，但str2有可能为空，此时返回整个str1；
3、str2可能存在重复的字符，此时str3需要包含相等数量该字符；

示例1

输入

"meituan2019","i2t"

输出

"ituan2"

备注:

str1，str2 的长度均不超过100

算法知识视频讲解

Python

Olive_f

class Solution:
    def getMinString(self , str1 , str2 ):
        # write code here
        if not str2:return str1
        minindex = len(str2)
        maxindex = 0
        flag = 0
        str3 = list(str1).copy()
        for i in str2:
            if i in str3:
                flag += 1
                minindex = min(str3.index(i),minindex)
                maxindex = max(str3.index(i),maxindex)
                str3[str3.index(i)] = " "
        return str1[minindex:maxindex+1]if flag == len(str2) else ""

发表于 2020-09-01 10:31:14 回复(1)

Python

牛客217460482号

class Solution:
    def getMinString(self,str1,str2):
        if str2 == '':
            return str1
        else:
            result = str()
            lis1 = list()
            for i in str2:
                for j in range(len(list(str1))):
                    if i==str1[j] and j not in lis1:
                        lis1.append(j)
                        break
                    elif i!=str1[j] and j==len(list(str1))-1:
                        lis1=[]
                        break
            if lis1 != []:
                lis1.sort()
                result = ''.join(str1[lis1[0]:lis1[-1]+1])
            return result

发表于 2020-06-09 17:11:24 回复(0)

Python

Bonhill7

class Solution:
    def getMinString(self , str1 , str2 ):
        # write code here
        str1l=list(str1)
        str2l=list(str2)
        if len(str2)==0:
            return str1
        tmp1=str1l.copy()
        p=[]
        for i in range(len(str2)):
            x=0
            for j in range(len(str1)):
                if tmp1[j]==str2l[i]:
                    p.append(j)
                    tmp1[j]=" "
                    x=1
                    break
            if x==0:
                return ""
        return(str1[min(p):max(p)+1])

用列表存，暴力遍历对应字符所在位置，完事

发表于 2020-03-13 14:57:28 回复(4)