百度前端算法题

题目描述

     输入第一行输入一串只含01的字符串，第二行输入n个问号(?)，第三行输出．可以看做字符串匹配问题．假设牛牛输入第一行输入＂010101＂,第二行输入??（即2个问号)．从字符串的第一个开始看，可以分别分为"01" "10" "01" "10" "01"总共有五种，但是去掉重复的只有"01" "10"两种．故输出２．

解题思路

     开始想着就是字符串匹配问题，第二个字符串的长度做全排列，就可以得到需要匹配得子串．以第二个字符串的长度作为匹配第一个字符串的步长．这样做暴力直观，但是很不划算，因为既要对第一个字符串的每一个切片和得到的全排列进行依次比较，还要对记录是否匹配成功的问题．记第一个字符串长度为n,第二个字符串长度为k这样的话，匹配的时间复杂度为O(n*(2^k))，还需要一个数组记录是否匹配成功,空间复杂度为O(2^k).在最后还需要进行统计，时间复杂度为O(2^k).看来这是很笨拙的算法了．
    于是，换个思路，发现题目给出的字符串很特别啊，全是01组合，这就不难想到了二进制．根据算法第一节课老师讲的一个例子．在很多数据中找出某个数据是否重复的方法，好像有了优化的方案．
    所以，就有下面稍微简便一点的算法．我们也先申请个大小为2^k的数组，作用同上，用来记录是否匹配成功．这里有个小技巧，因为我们只需要两个值，匹配成功，匹配失败．我们可以把它申请成bit类型，１表示成功，０表示失败．遍历第一个字符串，每做一次，切片长度为k．这样每次就能得到一个长度为k的01字符串．把它和我们刚刚定义的数组联系起来．是不是恍然大悟呢？对，我们就把类似于＂0101＂切片看成二进制的数，化为十进制,把十进制数当做下标，找到对应位置填上1．举个栗子，＂0101＂看成二进制是0101,化为十进制为5,所以a[5]=1.这样遍历一次第一个字符串就可以出所有匹配的,时间复杂度O(n)．最后再遍历一次用来记录的数组计数输出,时间复杂度O(2^k)．空间复杂度为O(2^K).是不是简单了很多？

import math
def change(str):
    sum = 0
    for i in range(0, len(str)):
        if str[i] == '1':
            sum = sum + 1
        sum <<= 1
    sum >>= 1
    print(sum)
    return sum
str1 = input()
str2 = input()
length = len(str2)
l = int(math.pow(2,length))
list = []
for i in range(0,l):
    list.append(0)
for i in range(0,len(str1)-length):
    list[change(str1[i:i+length])] = 1
count = 0
for i in range(0,l):
    if list[i] == 1:
        count = count + 1
print(count)