Restituisce la stessa occorrenza di carattere in una lista di stringhe

1

Ho una matrice di stringhe ["abb", "bbxxaa"] .

Vorrei stampare tutti i caratteri che si presentano in uguale numero di volte in ogni indice, quindi nel caso di cui sopra stamperei bb perché si verificano due volte in entrambi gli indici e si verifica una volta e due volte rispettivamente nel primo e nel secondo indice.

Il mio approccio:

Tieni traccia solo dei caratteri nel primo indice e perché non dovremmo preoccuparci di altre lettere comunque. Quindi nel caso precedente terrei traccia della lettera a e b e controllo se si verificano la stessa volta nei prossimi indici.

Qualcuno può suggerire un modo migliore se possibile o sono sulla buona strada?

    
posta user2733436 22.10.2014 - 19:53
fonte

2 risposte

1

Sei partito bene, ma potresti considerare come funziona quando queste stringhe sono lunghe. Per ogni lettera nella prima stringa potresti finire confrontando ogni lettera della seconda stringa, prendendo il tempo che cresce come prodotto delle due dimensioni di stringa.

Un modo sarebbe di pre-elaborare entrambe le stringhe in modo che per una determinata lettera tu sappia quante volte succede. Se si è certi che questi sono caratteri a 8 bit, è possibile utilizzare due array int della dimensione 256, se si è sicuri di ripristinarli a zero. (in c ++ potrebbe essere più semplice creare un carattere nella mappa int). Per l'output, fai un loop del conteggio di ciascun carattere nella tua tabella e vedi se ha lo stesso conteggio nell'altra tabella.

Un modo leggermente diverso sarebbe quello di ordinare ogni stringa. Quindi puoi eseguire lo scan in avanti attraverso entrambe le stringhe allo stesso tempo.

    
risposta data 22.10.2014 - 20:58
fonte
0

Solo i caratteri di tracciamento della prima stringa sono una buona idea.

Puoi anche smettere di tracciare i caratteri dopo aver dimostrato che nella seconda stringa ci sono più caratteri del primo.

Quindi terrei un elenco di strutture {char_t character, int count_first, int count_second} per ogni carattere distinto della prima stringa. Per ogni carattere nella seconda stringa, analizzerei l'elenco e incrementerei count_second nell'elemento in cui character corrisponde al carattere corrente. Se count_first < count_second dopo, rimuoverei l'elemento dall'elenco.

Alla fine, filtrerei gli elementi dove count_first == count_second .

    
risposta data 22.10.2014 - 21:17
fonte

Leggi altre domande sui tag