Sounds like it was a coding challenge about https://en.wikipedia.org/wiki/Space%E2%80%93time_tradeoff

Depending on parameters N,M,Q as well as data and query distribution, the "best" algorithm will be different. A simple example, given the query ??? you know the answer — the length of the dictionary — without any computation 😸

In the general case, most likely, it pays to create a search index in advance (that is while reading the dictionary, before any query is seen).

I'd go with this: number the input 0 cat; 1 map; ...

Then build a search index per letter position:

index = [
  {"c": 0b00001, "m": 0b00010, ...}  # first query letter
  {"a": 0b01111, "e": 0x10000}       # second query letter
]

Prepare all = 0x11111 (all bits set) as "matches everything".

Then query lookup: ?a? ⇒ all & index[1]["a"] & all. †

Afterwards you'll need to count number of bits set in the result.

The time complexity of single query is therefore O(N) * (M + O(1)) ‡, which is a decent trade-off.

The entire batch is O(N*M*Q).

Python (as well as es2020) supports native arbitrary precision integers, which can be elegantly used for bitmaps, as well as native dictionaries, use them :) However if the data is sparse, an adaptive or compressed bitmap such as https://pypi.org/project/roaringbitmap may perform better.

† In practice ... & index[1].get("a", 0) & ... in case you hit a blank.

‡ Python data structure time complexity is reported O(...) amortised worst case while in CS O(...) worst case is usually considered. While the difference is subtle, it can bite even experienced developers, see e.g. https://bugs.python.org/issue13703

One approach could be to use Python's fnmatch module (for every pattern sum the matches in words):

import fnmatch

names = ['uqqur', 'lxzev', 'ydfgs']
patterns = ['?z???', '???i?', '???e?', '???f?', '?z???']
[sum(fnmatch.fnmatch(name, pattern) for name in names) for pattern in patterns]

# [0, 0, 1, 0, 0]

I don't know Python, but the gist of the naive algorithm looks like this:

#count how many words in Words list match a single query 
def DoQuery(Words, OneQuery):
    count = 0
    #for each word in the Words list
    for i in range(Words.size()):
        word = Words.at(i)
        #compare each letter to the query
        match = true
        for j in range(word.size()):
            wordLetter = word.at(j)
            queryLetter = OneQuery.at(j)
            #if the letters do not match and are not ?, then skip to next word
            if queryLetter != '?' and queryLetter != wordLetter:
                match = false
                break
        #if we did not skip, the words match. Increase the count
        if match == true
            count = count + 1
    #we have now checked all the words, return the count
    return count

Of course, this executes the innermost loop around 3.5x10^10 times, which might be too slow. So one would need to read in the dictionary, precompute some short of shortcut data structure, then use the shortcut to find the answers faster.

One shortcut data structure would be to make a map of possible queries to answers, making the query O(1). There are only 4.47*10^9 possible queries, so this is possibly faster.

A similar shortcut data structure would be to make a trie of possible queries to answers, making the query O(M). There are only 4.47*10^9 possible queries, so this is possibly faster. This is more complex code, but may also be easier to understand for some people.

Another shortcut would be to "assume" each query has exactly one non-question-mark, and make a map of possible queries to subset dictionaries. This would mean you'd still have to run the naive query on the subset dictionary, but it would be ~26x smaller, and thus ~26x faster. You'd also have to convert the real query into only having one non-question-mark to lookup the subset dictionary in the map, but that should be easy.

I guess my first try would have been to replace the ? with a . in the query, i.e. change ?at to .at, and then use those as regular expressions and match them against all the words in the dictionary, something as simple as this:

import re
for q in queries:
    p = re.compile(q.replace("?", "."))
    print(sum(1 for w in words if p.match(w)))

However, seeing the input sizes as N up to 5x10⁴ and Q up to 10⁵, this might be too slow, just as any other algorithm comparing all pairs of words and queries.

On the other hand, note that M, the number of letters per word, is constant and rather low. So instead, you could create Mx26 sets of words for all letters in all positions and then get the intersection of those sets.

from collections import defaultdict
from functools import reduce

M = 3
words = ["cat", "map", "bat", "man", "pen"]
queries = ["?at", "ma?", "?a?", "??n"]

sets = defaultdict(set)
for word in words:
    for i, c in enumerate(word):
        sets[i,c].add(word)

all_words = set(words)
for q in queries:
    possible_words = (sets[i,c] for i, c in enumerate(q) if c != "?")
    w = reduce(set.intersection, possible_words, all_words)
    print(q, len(w), w)

In the worst case (a query that has a non-? letter that is common to most or all words in the dictionary) this may still be slow, but should be much faster in filtering down the words than iterating all the words for each query. (Assuming random letters in both words and queries, the set of words for the first letter will contain N/26 words, the intersection for the first two has N/26² words, etc.)

This could probably be improved a bit by taking the different cases into account, e.g. (a) if the query does not contain any ?, just check whether it is in the set (!) of words without creating all those intersections; (b) if the query is all-?, just return the set of all words; and (c) sort the possible-words-sets by size and start the intersection with the smallest sets first to reduce the size of temporarily created sets.

About time complexity: To be honest, I am not sure what time complexity this algorithm has. With N, Q, and M being the number of words, number of queries, and length of words and queries, respectively, creating the initial sets will have complexity O(N*M). After that, the complexity of the queries obviously depends on the number of non-? in the queries (and thus the number of set intersections to create), and the average size of the sets. For queries with zero, one, or M non-? characters, the query will execute in O(M) (evaluating the situation and then a single set/dict lookup), but for queries with two or more non-?-characters, the first set intersections will have on average complexity O(N/26), which strictly speaking is still O(N). (All following intersections will only have to consider N/26², N/26³ etc. elements and are thus negligible.) I don't know how this compares to The Trie Approach and would be very interested if any of the other answers could elaborate on that.

It should be O(N) time and space approach given M is small and can be considered constant. You might want to look at implementation of Trie here.

Perform the first pass and store the words in Trie DS.

Next for your query, you perform a combination of DFS and BFS in the following order.

If you receive a ?, Perform BFS and add all the children. For non ?, Perform a DFS and that should point to the existence of a word.

For further optimization, a suffix tree may also be used for storage DS.

This question can be done by the help of Trie Data Structures. First add all words to trie ds. Then you have to see if the word is present in trie or not, there's a special condition of ' ?' So you have to take care for that condition also, like if the character is ? then simply go to next character of the word.

I think this approach will work, there's a similar Question in Leetcode.

Link : https://leetcode.com/problems/design-add-and-search-words-data-structure/

I think we can use trie to solve this problem. Initially, we will just add all the strings to the trie, and later when we get each query we can just check whether it exists in trie or not.

The only thing different here is the '?' but we can use it as an all char match, so whenever we will detect the '?' in our search string we will look what are all possible words possible from here and then simply do a dfs by searching the word in all possible paths.

Below is the C++ code

class Trie {
public:
bool isEnd;
vector<Trie*> children;
Trie() {
    this->isEnd = false;
    this->children = vector<Trie*>(26, nullptr);
}
};
Trie* root;

void insert(string& str) {
    int n = str.size(), idx, i = 0;
    Trie* node = root;
    while(i < n) {
        idx = str[i++] - 'a';
        if (node->children[idx] == nullptr) {
            node->children[idx] = new Trie();
        }
        node = node->children[idx];
    }
    node->isEnd = true;
}

int getMatches(int i, string& str, Trie* node) {
    int idx, n = str.size();
    while(i < n) {
        if (str[i] >= 'a' && str[i] <='z')
            idx = str[i] - 'a';
        else {
            int res = 0;
            for(int j = 0;j<26;j++) {
                if (node->children[j] != nullptr)
                    res += getMatches(i+1, str, node->children[j]);
            }
            return res;
         }
        
        if (node->children[idx] == nullptr) return 0;
        node = node->children[idx];
        ++i;
    }
    return node->isEnd ? 1 : 0;
}

int main() {
    int n, m;
    cin>>n>>m;
    string str;
    root = new Trie();
    while(n--) {
        cin>>str;
        insert(str);
    }
    int q;
    cin>>q;
    while(q--) {
        cin>>str;
        cout<<(str.size() == m ? getMatches(0, str, root) : 0)<<"\n";
    }
}

This is brute but Trie is a better implemntaion.

"""
Input: db whic is a list of words
chk :  str to find
"""

def check(db,chk):
    
    seen = collections.defaultdict(list)
    for i in db:
        for j in range(len(i)):
            temp = i[:j] + "?" + i[j+1:]
            seen[temp].append(i)
            
    return len(seen[chk])
    
print check(["cat","bat"], "?at")

You can use a simplified version of trie as the query string has pre-defined length. No need of ends variable in the Trie node

#include <bits/stdc++.h>
using namespace std;

typedef struct TrieNode_ {
    struct TrieNode_* nxt[26];
} TrieNode;

void addWord(TrieNode* root, string s) {
    TrieNode* node = root;
    for(int i = 0; i < s.size(); ++i) {
        if(node->nxt[s[i] - 'a'] == NULL) {
            node->nxt[s[i] - 'a'] = new TrieNode;
        }
        node = node->nxt[s[i] - 'a'];
    }
}

void matchCount(TrieNode* root, string s, int& cnt) {
    if(root == NULL) {
        return;
    }
    if(s.empty()) {
        ++cnt;
        return;
    }
    TrieNode* node = root;
    if(s[0] == '?') {
        for(int i = 0; i < 26; ++i) {
            matchCount(node->nxt[i], s.substr(1), cnt);
        }
    }
    else {
        matchCount(node->nxt[s[0] - 'a'], s.substr(1), cnt);
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<string> s(N);
    TrieNode *root = new TrieNode;
    for (int i = 0; i < N; ++i) {
        cin >> s[i];
        addWord(root, s[i]);
    }
    int Q;
    cin >> Q;
    for(int i = 0; i < Q; ++i) {
        string queryString;
        int cnt = 0;
        cin >> queryString;
        matchCount(root, queryString, cnt);
        cout << cnt << endl;
    }
}

Can I do it with ascii values like:

• for charcters in queryword calculate the ascii values sum.
• for words in dictionary, calculate ascii of words character wise and check it with ascii sum of query word, like for bat, if ascii of b matches ascii sum of queryword then increment count else calculate ascii of a and check with query ascii if not then add it to ascii of b then check and hence atlast return the count. How's this approach?

Notes: 1. This code doesn't read the input but instead takes params from main method. 2. For large inputs, we could use java 8 streams to parallelize the search process and improve the performance.

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class WordSearch {

private void matchCount(int N, int M, int Q, String[] words,  String[] queries) {
    
    Pattern p = null;
    Matcher m = null;
    int count = 0;
    
    for (int i=0; i<Q; i++) {
        
        p = Pattern.compile(queries[i].replace('?','.'));
        for (int j=0; j<N; j++) {
            m = p.matcher(words[j]);
            if (m.find()) {
                count++;    
            }
        }
        System.out.println("For query word '"+ queries[i] + "', the count is: " + count) ;
        count=0;
    }
    System.out.println("\n");
    
}


public static void main(String[] args) {
    
    WordSearch ws = new WordSearch();
    int N = 5; int M=3; int Q=4;
    String[] w = new String[] {"cat", "map", "bat", "man", "pen"};
    String[] q = new String[] {"?at", "ma?", "?a?", "??n" };
    ws.matchCount(N, M, Q, w, q); 
    
    w = new String[] {"uqqur", "1xzev", "ydfgz"}; 
    q = new String[] {"?z???", "???i?", "???e?", "???f?", "?z???"};
    N=3; M=5; Q=5;
    ws.matchCount(N, M, Q, w, q);
    
}

}

I can think of kind of trie with bfs for lookup approach

class Node:

def __init__(self, letter):
    self.letter = letter
    self.chidren = {}

@classmethod
def construct(cls):
    return cls(letter=None)

def add_word(self, word):
    current = self

    for letter in word:
        if letter not in current.chidren:
            node = Node(letter)
            current.chidren[letter] = node
        else:
            node = current.chidren[letter]
        current = node

def lookup_word(self, word, m):
    def _lookup_next_letter(_letter, _node):
        if _letter == '?':
            for node in _node.chidren.values():
                q.put((node, i))

        elif _letter in _node.chidren:
            q.put((_node.chidren[_letter], i))

    q = SimpleQueue()
    count = 0
    i = 0
    current = self

    letter = word[i]
    i += 1

    _lookup_next_letter(letter, current)

    while not q.empty():
        current, i = q.get()
        if i == m:
            count += 1
            continue

        letter = word[i]
        i += 1
        _lookup_next_letter(letter, current)

    return count

def __eq__(self, other):
    return self.letter == other.letter if isinstance(other, Node) else other

def __hash__(self):
    return hash(self.letter)