Prova a trovare una parola nel dizionario che ha dato più lettere

Il meglio che puoi fare è ridurre il numero di confronti con il numero di lettere nel dizionario.

cercato: a, e, o, g, z, k, l, j, w, n

1. crea l'indice dell'alfabeto dove le chiavi ricercate hanno valore 1, il resto: 0.

      index={a:1, b:0, c:0, d:0, e:1, f:0, g:1...}
   

2. Iterate su ogni parola del dizionario. Aggiungi il valore dell'indice alla somma di quella parola. Ricorda la posizione della parola e il valore se è maggiore del migliore.

   max=0;
   max_index=0;
   
   foreach(dictionary as position=>word)
   {
       sum=0;
       foreach(word as letter)
       {
         sum += index[letter];
       }
       if(sum > max)
       {
           max = sum;
           max_index = position;
       }
   }
   

max_index punta alla parola con il massimo delle lettere. Alcune ottimizzazioni possono saltare parole più brevi del massimo corrente o iniziare con un dizionario ordinato per lunghezza della parola e fermarsi una volta che la lunghezza della parola scende al massimo attualmente trovato.

Ciò presuppone che le lettere della lista possano ripetere un numero qualsiasi di volte. Se non lo sono, fai in modo che l'indice contenga il numero di un determinato tipo di lettere, incrementa la somma di 1 per ogni valore di indice diverso da zero e decrementa l'indice. (resetta l'indice su ogni riga.)

In questo momento le ottimizzazioni potrebbero essere, in aggiunta alle precedenti: interrompi la verifica della parola se rimangono meno delle lettere di massima somma, interrompi l'operazione se viene trovata la parola con tutte le lettere.

Vorrei aggiungere un po 'alla soluzione di SF. Non sono sicuro se sono corretto nella mia analisi, ma comunque:

Se la tua pre-elaborazione è gratuita (considerando che la ricerca verrà eseguita abbastanza volte) puoi pre-elaborare ogni parola in un dict producendo per essa un'entità come l'indice SF menzionato. Quindi ogni parola diventa un numero come

01000100011101.... (up to the last letter a set of words can consist of)

dove ogni 1 rappresenta se la parola ha questa lettera o no (saltiamo il caso in cui ha il doppio o più per semplicità).

Puoi inoltre organizzare questo dict trasformato in base alla quantità di lettere diverse della parola, per iniziare a cercare con quelle che contengono la maggior parte delle lettere ed essere in grado di interrompere la ricerca in anticipo una volta entrati nel range che non può avere più corrispondenze di quello che hai già.

Quando si itera su ogni parola di un dizionario (ora ridotta a numeri) si semplicemente XOR questo numero con il numero prodotto dall'insieme delle lettere che si sta cercando e si calcola il suo peso di hamming (il numero di 1s) che è essenzialmente cosa stai cercando.

link

Poiché la dimensione dell'input è sempre costante (la dimensione dell'alfabeto invece della dimensione variabile della parola) può essere eseguita in modo efficiente con algos disponibili pubblicamente. In questo modo non dovrai confrontare le lettere una per una. Gestire le lettere doppie / triple può essere fatto aumentando le strutture, suppongo.

Voglio solo fornire una soluzione alternativa. Se il numero di lettere casuali è piccolo, puoi provare a generare tutte le diverse permutazioni delle lettere e verificare se il dizionario contiene una permutazione.

Ad esempio, se hai solo 3 lettere "a", "b" e "c".

Tutte le permutazioni sono "abc", "bca", "cab", "ab", "bc", "ac", "a", "b" e "c". Puoi passare da quelli più lunghi al più breve e controllare se il dict contiene la parola. È più efficiente quando il dizionario è grande e il numero di lettere casuali è ridotto.