Parece que fue un desafío de codificación sobre https://en.wikipedia.org/wiki/Space%E2%80%93time_tradeoff

Dependiendo de los parámetros N, M, Q, así como de la distribución de datos y consultas, el "mejor" algoritmo será diferente. Un ejemplo simple, dada la consulta ??? sabes la respuesta, la longitud del diccionario, sin ningún cálculo 😸

En el caso general, lo más probable es que valga la pena crear un índice de búsqueda por adelantado (es decir, mientras lee el diccionario, antes de ver cualquier consulta).

Iría con esto: numere la entrada 0 cat; 1 map; ...

Luego crea un índice de búsqueda por posición de letra:

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

Prepare all = 0x11111 (todos los bits configurados) como "coincide con todo".

Entonces consulta de búsqueda: ?a? ⇒ all & index[1]["a"] & all . †

Luego, deberá contar la cantidad de bits establecidos en el resultado.

Por lo tanto, la complejidad de tiempo de una sola consulta es O(N) * (M + O(1)) ‡, lo cual es una compensación decente.

El lote completo es O(N*M*Q) .

Python (así como es2020) admite enteros nativos de precisión arbitraria, que se pueden usar con elegancia para mapas de bits, así como diccionarios nativos, utilícelos :) Sin embargo, si los datos son escasos, un mapa de bits adaptable o comprimido como https://pypi .org/project/roaringbitmap puede funcionar mejor.

† En la práctica ... & index[1].get("a", 0) & ... en caso de que quede en blanco.

‡ La complejidad temporal de la estructura de datos de Python se informa O(...) amortizado en el peor de los casos, mientras que en CS se suele considerar O(...) en el peor de los casos . Si bien la diferencia es sutil, puede molestar incluso a los desarrolladores experimentados, consulte, por ejemplo, https://bugs.python.org/issue13703

Un enfoque podría ser usar el módulo fnmatch de Python (para cada patrón, suma las coincidencias en palabras):

 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]

No conozco Python, pero la esencia del algoritmo ingenuo se ve así:

 #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

Por supuesto, esto ejecuta el bucle más interno unas 3,5x10^10 veces, lo que podría ser demasiado lento. Por lo tanto, uno necesitaría leer en el diccionario, precalcular una estructura de datos de acceso directo y luego usar el acceso directo para encontrar las respuestas más rápido.

Una estructura de datos de acceso directo sería hacer un mapa de posibles consultas a respuestas, haciendo la consulta O(1). Solo hay 4.47 * 10 ^ 9 consultas posibles, por lo que esto es posiblemente más rápido.

Una estructura de datos de acceso directo similar sería hacer una prueba de posibles consultas a respuestas, haciendo la consulta O (M). Solo hay 4.47 * 10 ^ 9 consultas posibles, por lo que esto es posiblemente más rápido. Este es un código más complejo, pero también puede ser más fácil de entender para algunas personas.

Otro atajo sería "asumir" que cada consulta tiene exactamente un signo que no es de interrogación y hacer un mapa de posibles consultas para subconjuntos de diccionarios. Esto significaría que aún tendría que ejecutar la consulta ingenua en el diccionario de subconjuntos, pero sería ~26 veces más pequeño y, por lo tanto, ~26 veces más rápido. También tendría que convertir la consulta real para que solo tenga un signo que no sea de interrogación para buscar el diccionario de subconjuntos en el mapa, pero eso debería ser fácil.

Supongo que mi primer intento habría sido reemplazar el ? con un . en la consulta, es decir, cambie ?at por .at , y luego utilícelas como expresiones regulares y compárelas con todas las palabras del diccionario, algo tan simple como esto:

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

Sin embargo, viendo los tamaños de entrada como N hasta 5x10 ⁴ y Q hasta 10 ⁵ , esto podría ser demasiado lento, al igual que cualquier otro algoritmo que compare todos los pares de palabras y consultas.

Por otro lado, tenga en cuenta que M , el número de letras por palabra, es constante y bastante bajo. Entonces, en su lugar, podría crear conjuntos de palabras Mx26 para todas las letras en todas las posiciones y luego obtener la intersección de esos conjuntos.

 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)

En el peor de los casos (una consulta que tiene una letra que no es ? que es común a la mayoría o a todas las palabras del diccionario), esto aún puede ser lento, pero debería ser mucho más rápido para filtrar las palabras que iterar todas las palabras para cada consulta. . (Suponiendo letras aleatorias tanto en las palabras como en las consultas, el conjunto de palabras de la primera letra contendrá N/26 palabras, la intersección de las dos primeras tendrá N/26² palabras, etc.)

Esto probablemente podría mejorarse un poco teniendo en cuenta los diferentes casos, por ejemplo (a) si la consulta no contiene ningún ? , solo verifique si está en el set (!) de palabras sin crear todas esas intersecciones; (b) si la consulta es todo- ? , solo devuelve el conjunto de todas las palabras; y (c) ordenar los conjuntos de palabras posibles por tamaño y comenzar la intersección con los conjuntos más pequeños primero para reducir el tamaño de los conjuntos creados temporalmente.

Acerca de la complejidad del tiempo: para ser honesto, no estoy seguro de qué complejidad de tiempo tiene este algoritmo. Siendo N, Q y M el número de palabras, el número de consultas y la longitud de las palabras y las consultas, respectivamente, la creación de los conjuntos iniciales tendrá una complejidad O(N*M). Después de eso, la complejidad de las consultas obviamente depende del número de no- ? en las consultas (y, por lo tanto, el número de intersecciones de conjuntos que se crearán) y el tamaño medio de los conjuntos. Para consultas con cero, uno o M non- ? caracteres, la consulta se ejecutará en O(M) (evaluando la situación y luego una sola búsqueda de conjunto/dict), pero para consultas con dos o más caracteres que no sean ? -caracteres, las intersecciones del primer conjunto tendrán en promedio una complejidad O(N/26), que estrictamente hablando sigue siendo O(N). (Todas las siguientes intersecciones solo tendrán que considerar elementos N/26², N/26³, etc. y, por lo tanto, son insignificantes). No sé cómo se compara esto con el enfoque Trie y estaría muy interesado si alguna de las otras respuestas pudiera elaborar en ese.

Debería ser un enfoque de tiempo y espacio O(N) dado que M es pequeño y puede considerarse constante. Es posible que desee ver la implementación de Trie aquí.

Realice el primer pase y almacene las palabras en Trie DS.

A continuación, para su consulta, realice una combinación de DFS y BFS en el siguiente orden.

Si recibe un ?, realice BFS y agregue todos los hijos. Para no ?, realice un DFS y eso debería apuntar a la existencia de una palabra.

Para una mayor optimización, también se puede utilizar un árbol de sufijos para el almacenamiento DS.

Esta pregunta se puede hacer con la ayuda de Trie Data Structures. Primero agregue todas las palabras a los intentos. Entonces tienes que ver si la palabra está presente en trie o no, hay una condición especial de ' ?' Entonces, también debes cuidar esa condición, como si el personaje lo fuera. luego simplemente vaya al siguiente carácter de la palabra.

Creo que este enfoque funcionará, hay una Pregunta similar en Leetcode.

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

Creo que podemos usar trie para resolver este problema. Inicialmente, solo agregaremos todas las cadenas al trie, y luego, cuando obtengamos cada consulta, podemos verificar si existe en trie o no.

Lo único diferente aquí es el '?' pero podemos usarlo como una coincidencia de todos los caracteres, por lo que siempre que detectemos el '?' en nuestra cadena de búsqueda, veremos cuáles son todas las palabras posibles desde aquí y luego simplemente haremos un dfs buscando la palabra en todas las rutas posibles.

A continuación se muestra el código C++

 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"; } }

Esto es bruto, pero Trie es una mejor implementación.

 """ 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")

Puede usar una versión simplificada de trie ya que la cadena de consulta tiene una longitud predefinida. No hay necesidad de variables de ends en el nodo Trie.

 #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; } }

¿Puedo hacerlo con valores ascii como:

• para charcters en queryword calcular la suma de valores ascii.
• para las palabras en el diccionario, calcule el ascii de las palabras según el carácter y compruébelo con la suma ascii de la palabra de consulta, como para bat, si el ascii de b coincide con la suma ascii de la palabra de consulta, entonces incremente el conteo; de lo contrario, calcule el ascii de a y verifique con la consulta ascii si no, entonces agréguelo a ascii de b, luego verifique y, por lo tanto, devuelva el conteo. ¿Cómo es este enfoque?

Notas: 1. Este código no lee la entrada sino que toma parámetros del método principal. 2. Para entradas grandes, podríamos usar flujos de Java 8 para paralelizar el proceso de búsqueda y mejorar el rendimiento.

 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); }

}

Puedo pensar en una especie de intento con bfs para el enfoque de búsqueda

 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)