13
\$\begingroup\$

I've written a function that searches for the nth occurrence of a character in the given string. A positive value for n will search from left-to-right, while a negative value will search from right-to-left. Zero is not a valid value for n.

Left-to-Right Search

"AABAXYAMN".NthIndexOf('A', 1) -> 0
"AABAXYAMN".NthIndexOf('A', 2) -> 1
"AABAXYAMN".NthIndexOf('A', 3) -> 3

Right-to-Left Search

"AABAXYAMN".NthIndexOf('A', -1) -> 6
"AABAXYAMN".NthIndexOf('A', -2) -> 3
"AABAXYAMN".NthIndexOf('A', -3) -> 1

Code:

/// <summary>
/// Searches for the nth occurrence of a character in the given string. A positive value for n will search from
/// left-to-right while a negative value will search from right-to-left. Zero is not a valid value for n.
/// </summary>
public static int NthIndexOf(this string input, char charToFind, int n) {
    int position;

    switch (Math.Sign(n)) {
        case 1:
            position = 0;
            while (((position = input.IndexOf(charToFind, position)) != -1) && ((--n) > 0)) { position++; }
            break;
        case -1:
            position = input.Length - 1;
            while (((position = input.LastIndexOf(charToFind, position)) != -1) && ((++n) < 0)) { position--; }
            break;
        default:
            throw new ArgumentOutOfRangeException(message: "param cannot be equal to 0", paramName: nameof(n));
    }

    return position;
}
\$\endgroup\$
7
\$\begingroup\$

First, your loops are evil to read. It took me several minutes to figure out what the condition did. Essentially, you loop N times, where N is the Nth instance of the character in the string you wish to find the index for. Each time you loop, you find the index of the next occurrence of the character in the string, update the position to search from, and continue the process until the index is either -1 (no Nth instance), or until n > 0 or n < 0, based on which side you are searching from.

A simpler way to write this algorithm is as follows:

public static int NthIndexOfC(this string input, char charToFind, int n)
{
    int position;

    switch (Math.Sign(n))
    {
        case 1:
            position = -1;
            do
            {
                position = input.IndexOf(charToFind, position + 1);
                --n;
            } while (position != -1 && n > 0);
            break;
        case -1:
            position = input.Length;
            do
            {
                position = input.LastIndexOf(charToFind, position - 1);
                ++n;
            } while (position != -1 && n < 0);
            break;
        default:
            throw new ArgumentOutOfRangeException(message: "param cannot be equal to 0", paramName: nameof(n));
    }

    return position;
}

It takes a little bit more room since I wrote the loop body on its own lines, but it is easy to understand, and there are no assignments in the loop condition.

However, this is still not the way I would write this algorithm. When you think about how IndexOf works, it iterates the string with a for loop from the specified starting index until it reaches the first instance of the requested character, which it returns. We can write similar behavior, but just keep track of which index we are at:

public static int NthIndexOf(this string input, char charToFind, int n)
{
    int count = 0;
    switch (Math.Sign(n))
    {
        case 1:
            for (var index = 0; index < input.Length; index++)
            {
                if (input[index] == charToFind)
                {
                    count++;
                }

                if (count == n)
                {
                    return index;
                }
            }
            break;
        case -1:
            for (var index = input.Length - 1; index >= 0; index--)
            {
                if (input[index] == charToFind)
                {
                    count++;
                }

                if (count == Math.Abs(n))
                {
                    return index;
                }
            }
            break;
        default:
            throw new ArgumentOutOfRangeException(message: "param cannot be equal to 0", paramName: nameof(n));
    }

    return -1;
}

This is the longest solution yet, but we aren't finished. Notice all that duplicated code?

public static int NthIndexOf(this string input, char charToFind, int n)
{
    switch (Math.Sign(n))
    {
        case 1:
            return NthIndexOf(input, charToFind, n, 0, input.Length);
        case -1:
            return NthIndexOf(input, charToFind, n, input.Length - 1, -1);
        default:
            throw new ArgumentOutOfRangeException(message: "param cannot be equal to 0", paramName: nameof(n));
    }
}

public static int NthIndexOf(string input, char charToFind, int n, int searchFrom, int searchTo)
{
    int count = 0;
    var index = searchFrom;

    while (index != searchTo)
    {
        if (input[index] == charToFind)
        {
            count++;
        }

        if (count == Math.Abs(n))
        {
            return index;
        }

        index += Math.Sign(n);
    }

    return -1;
}

There. Clean, easy to understand and maintain, and lots of options to use. Notice that the second NthIndexOf needs to have the searchTo one integer larger or smaller than the value you want to stop at to accommodate the multi-directional search.

\$\endgroup\$
  • \$\begingroup\$ Not really disagreeing with your point about the loops being ugly (I can see how they'd appear that way) but if read from right-to-left I personally found them to be even simpler than the do { ... } while(...) alternative. Interesting to see that the general opinion disagrees. I'll be trying out the manual iteration using your last example as a guide; the only thing I would change at first glance is the repeated calls to Math.Sign and Math.Abs that might add up unfavorably. \$\endgroup\$ – Kittoes0124 Dec 8 '16 at 19:22
  • \$\begingroup\$ Yes, keeping them separate might be a good idea if performance is critical. \$\endgroup\$ – Hosch250 Dec 8 '16 at 19:23
4
\$\begingroup\$

I don't think this method is very useful. It does simply too much. Make it the LINQ way and separate the logic into multiple methods.

Create two methods that search for the value and return an IEnumerable<int>:

public static IEnumerable<int> IndiciesOf(this string input, char value, int? startAt = null)
{
    startAt = startAt ?? 0;
    for (int i = startAt.Value; i < input.Length; i++)
    {
        if (input[i] == value)
        {
            yield return i;
        }
    }
}

public static IEnumerable<int> IndiciesOfReverse(this string input, char value, int? startAt = null)
{
    startAt = startAt ?? input.Length;
    for (int i = startAt.Value - 1; i >= 0; i--)
    {
        if (input[i] == value)
        {
            yield return i;
        }
    }
}

You could already use them in multiple scenarios. But let's go one step further and encapsulate your logic in two more extensions:

public static int NthIndexOf(this string input, char value, int n, int? startAt = null)
{
    return input
        .IndiciesOf(value, startAt)
        .Skip(n - 1)
        .DefaultIfEmpty(-1)
        .First();
}

public static int NthIndexOfReverse(this string input, char value, int n, int? startAt = null)
{
    return input
        .IndiciesOfReverse(value, startAt)
        .Skip(n - 1)
        .DefaultIfEmpty(-1)
        .First();
}

Or if you want to have only one method then try this (but make the other two private and add the suffix Internal - otherwise there'll be a conflict)

public static int NthIndexOf(this string input, char value, int n, int? startAt = null)
{
    return
        n >= 0
        ? input.NthIndexOf(value, n, startAt);
        : input.NthIndexOfReverse(value, n, startAt);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You'll need a DefaultIfEmpty(-1) to handle cases where skipping (n-1) items results in an empty collection. The method should return -1 when there isn't a valid index, not throw. \$\endgroup\$ – Servy Dec 9 '16 at 15:54
  • \$\begingroup\$ @Servy you're right, fixed and also changed the ugly if into ?: \$\endgroup\$ – t3chb0t Dec 9 '16 at 16:02
  • \$\begingroup\$ I like the approach but not very performant. Maybe name Forward and Reverse. \$\endgroup\$ – paparazzo Dec 9 '16 at 18:40
1
\$\begingroup\$

Pretty sure iterate the string once and add occurrence is more efficient than multiple calls to input.IndexOf. It has to skip forward by position multiple times.

For me it is also easier to read.

public int GetPosByCount(string s, char target, int n)
{
    if (String.IsNullOrEmpty(s))
        return -1;
    if (n > s.Length)
        return -1;
    if (n > 0)
    {
        int occurance = 0;
        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == target)
            {                      
                if (occurance == n-1)
                    return i;
                occurance++;
            }
        }
        return -1;
    }
    else if (n < 0)
    {
        int occurance = 0;
        for (int i = s.Length - 1; i >= 0; i--)
        {
            if (s[i] == target)
            {
                if (occurance == n+1)
                    return i;
                occurance--;
            }
        }
        return -1;
    }
    else
    {
        return -1;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Jamal Dec 8 '16 at 20:38
  • \$\begingroup\$ On my machine, this solution is just under twice as fast. Not 15 times faster. The code could do with some cleaning up though. e.g. occurance is actually spelled occurrence. Or just call it count. \$\endgroup\$ – RobH Dec 9 '16 at 8:51
  • \$\begingroup\$ @RobH Yes I went back and there was an error in the test. It is more like 2:1 but I have something else running on the machine so I cannot get good numbers right now. \$\endgroup\$ – paparazzo Dec 9 '16 at 13:15
1
\$\begingroup\$

By taking advantage of the Math.Sign operation and avoiding the use of IndexOf and LastIndexOf (as suggested by the great answers provided so far) I have come up with a version that avoids having two different algorithms.

I was really thrilled by the elegance of the answer given by @t3chb0t but, unfortunately, the state machine turns out to be roughly 5x slower even when I replace the LINQ calls with more efficient code. I also loved the thoroughness of the response by @Hosch250 as it gave me the idea that I could collapse the two algorithms into one and a solid foundation to work with.

There are some gymnastics being performed in the variable assignment in order to handle the loop direction and startIndex but other than that this feels far less "evil" than the original and it performs twice as fast to boot!

/// <summary>
/// Searches for the nth occurrence of a character in the given string. A positive value for n will search from
/// left-to-right while a negative value will search from right-to-left. Zero is not a valid value for n.
/// </summary>
public static int NthIndexOf(this string input, char charToFind, int n, int? startIndex = null) {
    if (startIndex < 0) { throw new ArgumentOutOfRangeException(message: "param cannot be less than 0", paramName: nameof(startIndex)); }

    var nSign = Math.Sign(n);
    var inputLength = ((input == null) ? 0 : input.Length);
    int index;
    int count;

    if (nSign == 1) {
        index = (startIndex ?? 0);
        count = (inputLength - index);
    }
    else if (nSign == -1) {
        index = (startIndex ?? (inputLength - 1));
        count = (index + 1);
    }
    else {
        throw new ArgumentOutOfRangeException(message: "param cannot be equal to 0", paramName: nameof(n));
    }

    while (count-- > 0) {
        if ((input[index] == charToFind) && ((n -= nSign) == 0)) {
            return index;
        }

        index += nSign;
    }

    return -1;
}
\$\endgroup\$
  • \$\begingroup\$ That's true, LINQ is a little bit slower... which is noticable only with 10mln loops for a string of length ~200 chars ;-) I got the same result: 5sec vs 1.2sec. \$\endgroup\$ – t3chb0t Dec 9 '16 at 20:20
  • \$\begingroup\$ @t3chb0t Believe me, I'm tempted but 10 million calls to this function isn't going to be unreasonable in real world scenarios and I have to respect the difference here. \$\endgroup\$ – Kittoes0124 Dec 9 '16 at 20:32
0
\$\begingroup\$

I know this is old, but this answer is the easiest.

You can use the extension function "AllIndexesOf" to get a list of indexes then you can grab the one you want:

List<int> indexes = "AAAXXXYYY".AllIndexesOf("A");
indexes.ElementAt(2);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.