Controleer op tekenset in een tekenreeks

Gegeven een reeks, hoe kunt u controleren of een reeks tekens bestaat (en hun locatie vinden) binnen de tekenreeks, zodat de tekens in dezelfde volgorde moeten staan, maar niet opeenvolgend.

bijvoorbeeld de tekenreeks "INEEDTOGETAHAIRCUT" en de set om {'O', 'E', 'G', 'T'} te vinden

Bedankt

(ps - ik heb al een brute-force poging geprobeerd maar het is verschrikkelijk en werkt niet!)

4
nou de charachters kunnen nergens in de string voorkomen, de moet sequentieel zijn, maar de volgorde doet er niet toe - hmmm ik kan zien waarom dat misschien onduidelijk klinkt. Ik weet niet zeker hoe ik het anders moet uitleggen
toegevoegd de auteur Biscuit128, de bron
OOOO is niet toegestaan ​​en ja 4 opeenvolgende charachters die voldoen aan de set OEGT
toegevoegd de auteur Biscuit128, de bron
Is een waarde van 'OOOO' toegestaan ​​of wilt u zoeken naar een combinatie van O E G en T?
toegevoegd de auteur Fischermaen, de bron
Vraag niet duidelijk. "Zolang ze elkaar volgen, kunnen ze in elke volgorde staan." Dat lijkt tegenstrijdig te zijn.
toegevoegd de auteur David Heffernan, de bron
Dus je moet 4 opeenvolgende tekens vinden in de testreeks die de set uitput {'O', 'E', 'G', 'T'}
toegevoegd de auteur David Heffernan, de bron
@ Akron Hmm. De nieuwe vraag is heel anders dan de opmerking van Ricki hierboven.
toegevoegd de auteur David Heffernan, de bron
Ik ben er vrij zeker van dat degene die de vraag heeft bewerkt, de logica ervan heeft gewijzigd. Ik denk niet dat het zo onduidelijk was ...
toegevoegd de auteur Akron, de bron

5 antwoord

Op voorwaarde dat ik niet 100% zeker weet wat je bedoelt met "de karakters volgen elkaar op", is hier een mogelijke benadering: genereer alle mogelijke permutaties van de tekensreeks en zoek naar de permutatie

using System;
using System.Collections.Generic;
class Program {

    static IEnumerable GetPermutations(string value) {
        if (value.Length == 1) {
            yield return value;
        } else {
            for (int i = 0; i < value.Length; ++i) {
                string a = value[i].ToString();
                foreach (string b in GetPermutations(value.Remove(i, 1))) {
                    yield return a + b;
                }
            }
        }
    }

    static void Main(string[] args) {

        string test = "INEEDTOGETAHAIRCUT";
        string chars = "OEGT";
        foreach (string to_find in GetPermutations(chars)) {
            int i = test.IndexOf(to_find);
            if (i != -1) {
                Console.WriteLine("Found {0} at index {1}", to_find, i);
            }
        }
    }
}
1
toegevoegd
Welnu, mijn enige probleem hiermee is de volgorde van complexiteit. Maar dat maakt waarschijnlijk niet uit voor de vrager.
toegevoegd de auteur Akron, de bron

Met System.Linq in uw gebruik kunt u dit doen:

"INEEDTOGETAHAIRCUT".ToCharArray().Any(c => c=='O' || c=='E' || c=='G' || c=='T');

Of schrijf een nieuwe uitbreidingsmethode om een ​​char-array als argument te accepteren.  Om een ​​"reeks" van tekens in een willekeurige volgorde te hebben, kunt u dit doen:

public static class MyExtensions
{

    public static bool ContainsAnySequenceOf(this String str, List charArray)
    {
        foreach (char c in charArray)
        {
            if (str.ToCharArray().Any(x => x == c))
            {
                charArray.Remove(c);
                return str.Substring(str.IndexOf(c), Math.Min(str.Length - str.IndexOf(c), charArray.Count)).ContainsAnySequenceOf(charArray);
            }
        }
        return false;
    }
}

Noem het dan zo:

"INEEDTOGETAHAIRCUT".ContainsAnySequenceOf(new List {'O','E','G','T'});
1
toegevoegd
OK. Ik begrijp je vraag nu beter en heb mijn antwoord bewerkt om dat te bereiken.
toegevoegd de auteur Andrea Colleoni, de bron
ahhh dat is perfect, maar helaas moet ik niet waar zijn in plaats van alleen maar waar of niet waar. Ik had dit eigenlijk moeten noemen: /
toegevoegd de auteur Biscuit128, de bron

Waarom zou je iets dat nog eenvoudiger is, niet alleen gebruiken om twee regels te gebruiken om te controleren wat je nodig hebt

string strCompare = "INEEDTOGETAHAIRCUT";
string strStringContains = ""AHRI"; 
var matchingString = strCompare.IndexOfAny(strStringContains.ToCharArray()) != -1;
then wrap the matchingString in an if(matchingString){ }//should return true or false
1
toegevoegd

Hier is een zeer onelegante aanpak van de oude school om het probleem op te lossen. Hoewel ik er zeker van ben dat een deel van de code efficiënter zou kunnen zijn, vermijdt het het opsommen van alle permutaties van de zoekreeks (zoals gebeurt in het antwoord dat u accepteerde). Doen dat duur zou kunnen worden.

static bool matchesPermutation(string test, string search)
{
    string remaining = search;
    for (int i = 0; i < test.Length; i++)
    {
        int pos = remaining.IndexOf(test[i]);
        if (pos == -1)
            return false;
        else
            remaining = remaining.Remove(pos, 1);
    }
    return true;
}

static int findPermutation(string test, string search)
{
    for (int i = 0; i < test.Length-search.Length+1; i++)
        if (matchesPermutation(test.Substring(i, search.Length), search))
            return i;
    return -1;
}

static void Main(string[] args)
{
    string test = "INEEDTOGETAHAIRCUT";
    string search = "AHRI";
    int foundPos = findPermutation(test, search);
    Console.WriteLine(foundPos);
    if (foundPos != -1)
        Console.WriteLine(test.Substring(foundPos, search.Length));
}
0
toegevoegd

Als ik uw vraag goed begrijp:

U kunt String.IndexOfAny() gebruiken om het eerste teken van de volgorde.

Voer vervolgens de volgende tekens in de tekenreeks uit om te controleren of elk teken in de reeks legale tekens voorkomt. Voor elk personage dat u in uw lijst aantreft (inclusief het eerste dat u hebt gevonden), verwijdert u het uit de lijst met juridische tekens die kunnen volgen, om duplicaten te weigeren.

Als je een illegaal teken raakt, is de tekst geen overeenkomst, dus ga terug naar het begin van dit algoritme om het resterende deel van de reeks te verwerken.

Als je alle legale tekens achter elkaar vindt, heb je je resultaat.

0
toegevoegd
die de index van het eerste voorkomen van een willekeurig personage uit mijn set teruggeeft in tegenstelling tot het eerste exemplaar waarbij ze allemaal tegelijk verschijnen als dat logisch is?
toegevoegd de auteur Biscuit128, de bron
Maar dat voldoet niet aan de behoefte "aangezien de personages elkaar volgen"
toegevoegd de auteur Fischermaen, de bron
Sorry, de vraag was een beetje onduidelijk. Mijn antwoord bijgewerkt met een beetje meer hulp.
toegevoegd de auteur Jason Williams, de bron
Dit zijn mijn Perl-gewoonten.
toegevoegd de auteur iehrlich, de bron