匹配两个字符串列表，其中一个列表可以包含带有通配符'？'的字符串

Question

所以我的问题指出：

我有一个N个小写字母字符串的列表，每个字符串的长度为M。我们称它为S

例如：对于m = 3 {aab，aac，aba，abc，bab，bac，bba}

然后我有一个Q查询字符串，它的长度也为m，并且包含小写字符和'？'。

对于与查询字符串匹配的字符串的每个查询字符串返回计数。

注意：'？'等于任何字符。

示例：

对于查询字符串'a？b'answer = 1，{aab}

对于查询字符串'a ??' answer = 4，{aab，aac，aba，abc}等。

到目前为止我做了什么

BRUTE FORCE

for each query q:
   count=0
   iterate over the list of String in s:S
      if q.charAt(i) != '?' || s.charAt(i) != q.charAt(i)
        flag=false;
        break; 
   if flag==true
     count+=1
   print count 

时间：O（Q * N * M）

我想出了另一种使用二进制搜索的方法：

• 排序字符串列表。
• 将字符串列表考虑为N * M个字符的网格
• 对于每个查询字符串，而不是匹配列表中的每个字符串，以递归方式逐字符匹配。
• 当字符匹配时，考虑仅匹配的字符串集。例如：对于位置pos处的字符，如果Grid [l] [pos]到Grid [r] [pos]匹配，则将Grid的此子集传递给递归调用。
• 如果pos处的字符是'？'然后将[a ... z]中的值分配给角色，并在此位置求解每个值。

伪代码：

function: (l,r) binarySearch(List, ch, start, end);

function recursion(List, query, pos, start, end)
  result=0
  if query.charAt(pos) != '?'
    (l,r) binarySearch(List, query.charAt(pos), start, end)
    if pos = query.length:
       return length(l,r)
    if (l,r) not empty:
     result += recursion(List, query, pos+1, l, r)
  else
   if pos = query.length
      return length(start,end)
   for ch in [a...z]
     (l,r) binarySearch(List, ch, start, end)
     if (l,r) not empty:
       result+=recursion(List, query, pos+1, l, r)
  return result

function doSomething(List, Query)
  List : sort the list alphabetically
  for each query in Query:
    ans = recursion(List, query, 0, 0, N)

最坏的情况：

如果所有查询字符串都是[???，???，??? ...]则结果为O（Q * N * M）。仍然比蛮力似乎更好。

仍然感觉我们是否可以事先对列表进行预处理，并在更短的时间内回答Q查询。我无法弄清楚预处理的逻辑，因此查询将花费更少的时间。任何帮助表示赞赏。

Answer 1

要预处理给定的N个字符串，您可以构建一个Trie，然后在查询时可以逐级下降（每个字符为一个级别）。如果你有 '？'在任何级别（在查询字符串中）中，您都需要访问所有相邻节点，否则仅深度遍历就足够了。这将减少您在班轮中的搜索时间。深度==>给定搜索字符串的最大长度。