string - 这个编程问题的算法是什么？

Question

这是我在测试中遇到的一个问题，我无法解决。每次我想到一个算法时，都会出现一个新的极端案例，它失败了。有人可以解释一下，如何解决这个问题吗？

问题陈述

Cytes彩票是世界上最大的彩票。每张票上都有一串 az 字母。公司生产抽签字符串 S。如果他/她的票串是抽签字符串的特殊子串，则某人获胜。特殊子串是可以通过忽略drawString中最多K个字符形成的子串。例如，如果 draw string = "xyzabc" 并且彩票是 [ac zb yhja] 且 K=1，那么中奖彩票将是 2 即 ac（通过忽略拉绳中的“b”赢得）和 zb（通过忽略“a”赢得在拉绳中）。

现在有些人为了中彩票而改变他们的票串。为避免任何怀疑，他们可以对字符串进行以下更改。

1. 他们可以将字符“o”更改为字符“a”，反之亦然
2. 他们可以将字符“t”更改为字符“l”，反之亦然
3. 他们可以从字符串中的任何位置删除一个字符

请注意，他们最多可以忽略抽奖字符串中的“K”个字符，以与票证字符串匹配。

编写一个算法来找出中奖的人数（无论是诚实还是作弊）。

输入：

输入的第一行包含一个整数 - numTickets，表示票的数量（N）。第二行由一个字符串组成——drawString，表示绘制字符串（S）。第三行由 N 个空格分隔的字符串组成——ticket1、ticket2、…………，ticketN 代表门票。

最后一行包含一个整数容差，表示可以从 drawString(K) 中删除的最大字符数。

输出：

一个整数，表示中奖彩票的数量（公平或作弊）。

约束：

0 <= numTickets <= 1000
0 <= length of drawString <= 200
0 <= length of tickets[i] <= 200
0 <= tolerance <= 1000

笔记：

drawString 包含小写英文字母

例子：

输入：

3
aabacd
abcde aoc actld
1

输出：

2

标签： stringalgorithmdata-structures