Controleer op tekenset in een tekenreeks

Question

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

toegevoegd 27 oktober 2011 op 08:53 de auteur Biscuit128 bewerkt 27 oktober 2011 op 09:10

Bekeken: 2

de bron

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 27 oktober 2011 op 08:58, de auteur Biscuit128, de bron

OOOO is niet toegestaan en ja 4 opeenvolgende charachters die voldoen aan de set OEGT

toegevoegd 27 oktober 2011 op 09:03, 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 27 oktober 2011 op 09:02, de auteur Fischermaen, de bron

Vraag niet duidelijk. "Zolang ze elkaar volgen, kunnen ze in elke volgorde staan." Dat lijkt tegenstrijdig te zijn.

toegevoegd 27 oktober 2011 op 08:57, 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 27 oktober 2011 op 09:01, de auteur David Heffernan, de bron

@ Akron Hmm. De nieuwe vraag is heel anders dan de opmerking van Ricki hierboven.

toegevoegd 27 oktober 2011 op 09:37, 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 27 oktober 2011 op 09:11, 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 27 oktober 2011 op 09:10 de auteur Paolo Tedesco

de bron

Welnu, mijn enige probleem hiermee is de volgorde van complexiteit. Maar dat maakt waarschijnlijk niet uit voor de vrager.

toegevoegd 27 oktober 2011 op 09:41, de auteur Akron, de bron

de auteur Andrea Colleoni · Answer 1 · 2011-10-27T09:05Z

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

de auteur MethodMan · Answer 2 · 2011-11-10T07:52Z

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

de auteur David Heffernan · Answer 3 · 2011-10-27T09:25Z

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

de auteur Jason Williams · Answer 4 · 2011-10-27T08:58Z

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.