CODEWITHSUNDEEP
c#string
Biscuit128
Biscuit128

Reputation: 5398

Check for set of characters in a string

Given a string, how can you check if a set of characters exist (and find their location) inside the string such that the characters need to be in the same order but not consecutive.

for example the string "INEEDTOGETAHAIRCUT" and the set to find {'O','E','G','T'}

Thanks

(ps - i have already tried a brute force attempt but it is terrible and doesn't work!)

Upvotes: 4

Views: 6825

Answers (5)

MethodMan
MethodMan

Reputation: 18843

Why not use something even more simple only to two lines to check what you need

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

Upvotes: 1

Andrea Colleoni
Andrea Colleoni

Reputation: 6021

With System.Linq in your usings you can do this:

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

Or write a new extension method to accept a char array as the argument. To have any "sequence" of chars in any order you can do this:

public static class MyExtensions
{

    public static bool ContainsAnySequenceOf(this String str, List<char> 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;
    }
}

Then call it like this:

"INEEDTOGETAHAIRCUT".ContainsAnySequenceOf(new List<char> {'O','E','G','T'});

Upvotes: 1

David Heffernan
David Heffernan

Reputation: 612804

Here is a very inelegant old school approach to solving the problem. Although I'm sure some of the code could be more efficient, it avoids enumerating all permutations of the search set (as is done in the answer you accepted). Doing that could get expensive.

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

Upvotes: 0

Paolo Tedesco
Paolo Tedesco

Reputation: 57172

Provided I'm not 100% sure of what you mean with "the characters follow each other", here is a possible approach: generate all the possible permutations of the characters sequence and search for the permutation

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

    static IEnumerable<string> 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);
            }
        }
    }
}

Upvotes: 1

Jason Williams
Jason Williams

Reputation: 57892

If I understand your question correctly:

You can use String.IndexOfAny() to find the first character of the sequence.

Then iterate over the following characters in the string to check that each of them is included in the set of legal characters. For each character you find from your list (including the first one you found), remove it from the list of legal characters that can follow, to disallow duplicates.

If you hit an illegal character, the text isn't a match, so go back to the beginning of this algorithm to process the remaining part of the string.

If you find all the legal characters in a row, then you have your result.

Upvotes: 0

Related Questions