Test per caratteri ripetuti in una stringa

Question

Sto lavorando con le stringhe e ho uno scenario in cui ho bisogno di determinare se una stringa (solitamente una piccola < 10 caratteri) contiene caratteri ripetuti.

`ABCDE` // does not contain repeats 
`AABCD` // does contain repeats, ie A is repeated 

posso scorrere lo string.ToCharArray() e testare ogni personaggio contro ogni altro personaggio del char [], ma mi sento come mi manca qualcosa ovvio .... forse ho solo bisogno di caffè. Qualcuno può aiutare?

EDIT:

La stringa verrà ordinato, in modo da ordine non è importante in modo ABCDA => AABCD

La frequenza di ripetizioni è anche importante, quindi ho bisogno di sapere se la ripetizione è coppia o tripletta ecc.

Answer 1

Se la stringa è breve, solo il looping e il test potrebbero essere il modo più semplice ed efficace. Voglio dire che tu potresti creare un set di hash (in qualunque piattaforma tu stia usando) e scorrere tra i personaggi, fallendo se il personaggio è già nel set e aggiungendolo al set in altro modo - ma è probabile che fornisca qualche beneficio quando le corde sono più lunghe

EDIT: Ora che sappiamo che è ordinato, mquander's answer è il migliore IMO. Ecco un'implementazione:

public static bool IsSortedNoRepeats(string text) 
{ 
    if (text.Length == 0) 
    { 
     return true; 
    } 
    char current = text[0]; 
    for (int i=1; i < text.Length; i++) 
    { 
     char next = text[i]; 
     if (next <= current) 
     { 
      return false; 
     } 
     current = next; 
    } 
    return true; 
} 

A breve alternativa, se non ti dispiace ripetere l'uso indicizzatore:

public static bool IsSortedNoRepeats(string text) 
{ 
    for (int i=1; i < text.Length; i++) 
    { 
     if (text[i] <= text[i-1]) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

EDIT: Okay, con il lato "frequenza", mi trasformerò il problema rotonda un po. Devo ancora supporre che la stringa sia ordinata, quindi quello che vogliamo sapere è la lunghezza della corsa più lunga. Quando non ci sono ripetizioni, la lunghezza della corsa più lunga sarà 0 (per una stringa vuota) o 1 (per una stringa non vuota). Altrimenti, saranno 2 o più.

Prima una versione specifica stringa:

public static int LongestRun(string text) 
{ 
    if (text.Length == 0) 
    { 
     return 0; 
    } 
    char current = text[0]; 
    int currentRun = 1; 
    int bestRun = 0; 

    for (int i=1; i < text.Length; i++) 
    { 
     if (current != text[i]) 
     { 
      bestRun = Math.Max(currentRun, bestRun); 
      currentRun = 0; 
      current = text[i]; 
     } 
     currentRun++; 
    } 
    // It's possible that the final run is the best one 
    return Math.Max(currentRun, bestRun); 
} 

Ora possiamo anche fare questo come un metodo di estensione generale sulla IEnumerable<T>:

public static int LongestRun(this IEnumerable<T> source) 
{ 
    bool first = true; 
    T current = default(T); 
    int currentRun = 0; 
    int bestRun = 0; 

    foreach (T element in source) 
    { 
     if (first || !EqualityComparer<T>.Default(element, current)) 
     { 
      first = false; 
      bestRun = Math.Max(currentRun, bestRun); 
      currentRun = 0; 
      current = element; 
     } 
    } 
    // It's possible that the final run is the best one 
    return Math.Max(currentRun, bestRun); 
} 

Quindi è possibile chiamare "AABCD".LongestRun() per esempio.

Answer 2

Aggiornamento Ora, è necessario disporre di una serie di contatori per mantenere un conteggio.

Mantieni un array di bit, con un bit che rappresenta un carattere univoco. Attiva il bit quando incontri un personaggio ed esegui una volta la stringa. Una mappatura dell'indice di array di bit e del set di caratteri spetta a te decidere. Break se vedi che un particolare bit è già attivo.

Answer 3

Se la stringa è ordinata, è sufficiente ricordare ogni carattere a turno e verificare che il prossimo carattere non sia mai identico all'ultimo carattere.

Oltre a ciò, per le stringhe con meno di dieci caratteri, testare ogni personaggio contro tutto il resto è probabilmente più veloce o più veloce della maggior parte delle altre cose. Un vettore bit, come suggerito da un altro commentatore, potrebbe essere più veloce (aiuta se hai un piccolo set di caratteri legali.)

Bonus: ecco una soluzione LINQ chiazza di petrolio per implementare la funzionalità di Jon:

int longestRun = 
    s.Select((c, i) => s.Substring(i).TakeWhile(x => x == c).Count()).Max(); 

Quindi, OK, non è molto veloce! Hai un problema con quello ?!

:-)

Answer 4

Penso che il modo più semplice per raggiungere questo obiettivo è quello di utilizzare questa semplice espressione regolare

bool foundMatch = false; 
foundMatch = Regex.IsMatch(yourString, @"(\w)\1"); 

Se avete bisogno di ulteriori informazioni circa la partita (inizio, durata, ecc)

 Match match = null; 
    string testString = "ABCDE AABCD"; 
    match = Regex.Match(testString, @"(\w)\1+?"); 
    if (match.Success) 
    { 
     string matchText = match.Value; // AA 
     int matchIndnex = match.Index; // 6 
     int matchLength = match.Length; // 2 
    } 

Answer 5

/(.).*\1/ 

(o qualunque sia l'equivalente nella sintassi della libreria regex)

Non è il più efficiente, poiché probabilmente tornerà indietro a ogni carattere nella stringa e quindi eseguirà nuovamente la scansione in avanti. E di solito non sostengo espressioni regolari. Ma se si vuole brevità ...

Answer 6

Dal momento che si sta utilizzando 3.5, si potrebbe fare questo nella query LINQ uno:

var results = stringInput 
    .ToCharArray() // not actually needed, I've left it here to show what's actually happening 
    .GroupBy(c=>c) 
    .Where(g=>g.Count()>1) 
    .Select(g=>new {Letter=g.First(),Count=g.Count()}) 
; 

Per ogni personaggio che appare più di una volta l'ingresso, questo darà tu il personaggio e il numero di occorrenze.

Answer 7

Questo vi dirà molto rapidamente se una stringa contiene duplicati:

bool containsDups = "ABCDEA".Length != s.Distinct().Count(); 

E 'solo controlla il numero di caratteri distinti contro la lunghezza originale. Se sono diversi, hai duplicati ...

Modifica: Immagino che questo non si preoccupi della frequenza dei duplicati che hai notato nella tua modifica però ... ma alcuni altri suggerimenti qui già abbi cura di questo, quindi non posterò il codice perché noto che alcuni di essi ti offrono già una soluzione ragionevolmente elegante. Mi piace particolarmente l'implementazione di Joe con le estensioni LINQ.

Answer 8

ne dite qualcosa di simile:

string strString = "AA BRA KA DABRA"; 

var grp = from c in strString.ToCharArray() 
     group c by c into m 
     select new { Key = m.Key, Count = m.Count() }; 

foreach (var item in grp) 
{ 
    Console.WriteLine(
     string.Format("Character:{0} Appears {1} times", 
     item.Key.ToString(), item.Count)); 
} 

Answer 9

Quando non c'è fine di lavorare su di voi potrebbe usare un dizionario per mantenere i conteggi:

String input = "AABCD"; 
var result = new Dictionary<Char, int>(26); 
var chars = input.ToCharArray(); 
foreach (var c in chars) 
{ 
    if (!result.ContainsKey(c)) 
    { 
     result[c] = 0; // initialize the counter in the result 
    } 
    result[c]++; 
} 

foreach (var charCombo in result) 
{ 
    Console.WriteLine("{0}: {1}",charCombo.Key, charCombo.Value); 
} 

Answer 10

La soluzione hash Jon stava descrivendo è probabilmente il migliore. È possibile utilizzare un HybridDictionary poiché funziona bene con insiemi di dati piccoli e grandi. Dove la lettera è la chiave e il valore è la frequenza. (Aggiorna la frequenza ogni volta che l'aggiunta fallisce o HybridDictionary restituisce true per .Contains (chiave))

Answer 11

Ho iniziato a cercare alcune informazioni sulla rete e sono arrivato alla seguente soluzione.

string input = "aaaaabbcbbbcccddefgg"; 
     char[] chars = input.ToCharArray(); 
     Dictionary<char, int> dictionary = new Dictionary<char,int>(); 

     foreach (char c in chars) 
     { 
      if (!dictionary.ContainsKey(c)) 
      { 
       dictionary[c] = 1; // 
      } 
      else 
      { 
       dictionary[c]++; 
      } 
     } 

     foreach (KeyValuePair<char, int> combo in dictionary) 
     { 
      if (combo.Value > 1) //If the vale of the key is greater than 1 it means the letter is repeated 
      { 
       Console.WriteLine("Letter " + combo.Key + " " + "is repeated " + combo.Value.ToString() + " times"); 
      } 

     } 

Spero che aiuta, ho avuto un colloquio di lavoro in cui l'intervistatore mi ha chiesto di risolvere questo e capisco che è una domanda comune.