首页 > 试题广场 >

单双难全

[编程题]单双难全

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

有n个只包含小写字母的串 $s_1,s_2,..s_n$ ，每次给你一个只包含小写字母的串t。如果串S存在前缀S'，它的奇数位的字符与t的奇数位字符完全相同，称S为t的单匹配串，如果串S的偶数位字符与t的偶数位的字符全都相同，称S为t的双匹配串。

现在给你m个字符串，对于每个字符串 $t_i$ ，求 $s_1,s_2,...s_n$ 中有多少个串是t的单匹配串但不是t的双匹配串。

示例1

输入

3,["abc", "bbc", "cbd"],3,["abc","cad","bac"]

输出

[0,1,1]

说明

对于字符串"abc"。没有满足条件的单匹配串
字符串“cad"有满足条件的串: "cbd" ,第一个位置都是c，第三个位置都是d，是单匹配串，但是第二个位置不同，不是双匹配串
字符串"bac"有满足条件的串: "bbc" ,第一个位置都是b，第三个位置都是c，是单匹配串，但是第二个位置不同，不是双匹配串

备注:

算法知识视频讲解

Python 3

行走的三百斤

暴力求解：

依次遍历 t 取出元素 i_t，再取出 s 中元素 i_s :

通过 i_t[0] == i_s[0] 去除 s 中非 i_t 单匹配串的字符串，再比较 i_t == i_s[: len(i_t)]，去除满足双匹配的字符串。

在统计剩余字符串中满足单匹配串的个数。

class Solution:
    def solve(self, n, s, m, t):
        # write code here
        res = []
        for it in t:
            temp_it = self.get_single_str(it)
            check_len = len(temp_it)
            tStr_len = len(it)
            temp = [self.get_single_str(i)[:check_len] for i in s
                    if (i[:tStr_len] != it if tStr_len > 1 else True) and i[0] == it[0]]

            res.append(temp.count(temp_it))
        return res

    def get_single_str(self, s: str):
        return ''.join([s[i] for i in range(len(s)) if i % 2 == 0])

编辑于 2021-07-13 22:38:22 回复(0)