More efficient way to get all indexes of a character in a string

Question

Instead of looping through each character to see if it's the one you want then adding the index your on to a list like so:

     var foundIndexes = new List<int>();
     for (int i = 0; i < myStr.Length; i++)
     {
        if (myStr[i] == 'a')
           foundIndexes.Add(i);
     }

Answer 1

You can use String.IndexOf, see example below:

    string s = "abcabcabcabcabc";
    var foundIndexes = new List<int>();

    long t1 = DateTime.Now.Ticks;
    for (int i = s.IndexOf('a'); i > -1; i = s.IndexOf('a', i + 1))
        {
         // for loop end when i=-1 ('a' not found)
                foundIndexes.Add(i);
        }
    long t2 = DateTime.Now.Ticks - t1; // read this value to see the run time

Answer 2

I use the following extension method to yield all results:

public static IEnumerable<int> AllIndexesOf(this string str, string searchstring)
{
    int minIndex = str.IndexOf(searchstring);
    while (minIndex != -1)
    {
        yield return minIndex;
        minIndex = str.IndexOf(searchstring, minIndex + searchstring.Length);
    }
}

usage:

IEnumerable<int> result = "foobar".AllIndexesOf("o"); // [1,2]

Side note to a edge case: This is a string approach which works for one or more characters. In case of "fooo".AllIndexesOf("oo") the result is just 1 https://dotnetfiddle.net/CPC7D2

Answer 3

How about

string xx = "The quick brown fox jumps over the lazy dog";

char search = 'f';

var result = xx.Select((b, i) => b.Equals(search) ? i : -1).Where(i => i != -1);

Answer 4

The raw iteration is always better & most optimized.

Unless it's a bit complex task, you never really need to seek for a better optimized solution...

So I would suggest to continue with :

var foundIndexes = new List<int>();

for (int i = 0; i < myStr.Length; i++)

     if (myStr[i] == 'a') foundIndexes.Add(i);

Answer 5

If the string is short, it may be more efficient to search the string once and count up the number of times the character appears, then allocate an array of that size and search the string a second time, recording the indexes in the array. This will skip any list re-allocations.

What it comes down to is how long the string is and how many times the character appears. If the string is long and the character appears few times, searching it once and appending indicies to a List<int> will be faster. If the character appears many times, then searching the string twice (once to count, and once to fill an array) may be faster. Exactly where the tipping point is depends on many factors that can't be deduced from your question.

If you need to search the string for multiple different characters and get a list of indexes for those characters separately, it may be faster to search through the string once and build a Dictionary<char, List<int>> (or a List<List<int>> using character offsets from \0 as the indicies into the outer array).

Ultimately, you should benchmark your application to find bottlenecks. Often the code that we think will perform slowly is actually very fast, and we spend most of our time blocking on I/O or user input.

Answer 6

    public static List<int> GetSubstringLocations(string text, string searchsequence)
    {
        try
        {
            List<int> foundIndexes = new List<int> { };

            int i = 0;
            while (i < text.Length)
            {
                int cindex = text.IndexOf(searchsequence, i);

                if (cindex >= 0)
                {
                    foundIndexes.Add(cindex);
                    i = cindex;
                }

                i++;

            }

            return foundIndexes;
        }
        catch (Exception ex) { }
        return new List<int> { };
    }

Answer 7

public static String[] Split(this string s,char c = '\t')
    {
        if (s == null) return null;
        var a = new List<int>();
        int i = s.IndexOf(c);
        if (i < 0) return new string[] { s };
        a.Add(i);
        for (i = i+1; i < s.Length; i++) if (s[i] == c) a.Add(i);
        var result = new string[a.Count +1];            
        int startIndex = 0;
        result[0] = s.Remove(a[0]);
        for(i=0;i<a.Count-1;i++)
        {
            result[i + 1] = s.Substring(a[i] + 1, a[i + 1] - a[i] - 1);
        }
        result[a.Count] = s.Substring(a[a.Count - 1] + 1);
        return result;
    }

Answer 8

Another solution with less code:

public static int[] IndexOfAll(this string source, char target)
{
    return source.Select((c, idx) => c == target ? idx : -1).Where(idx => idx != -1).ToArray();
}

usage:

var result = "foobar".IndexOfAll('o'); // [1,2]