4
\$\begingroup\$

I've a list of names that I'd like to iterate over and extract from it those names that have two letters that are the same right next to each other (i.e. Bill, Terry, Debby, Aaron, etc.).

The below code I have accomplishes this task, however I was wondering if there was a more efficient or line-friendly method of approaching this problem.

I started thinking about a solution involving LINQ's Where<> method, but then I wasn't sure how to use both a string variable and an int index variable inside a lambda expression.

Also, does there exist a way to accomplish this task in faster than O(n^2) time?

public static List<string> DoubleLetters(string[] array)
{
    List<string> doubleLetter = new List<string>();
    for (int i = 0; i < array.Length; i++)
    {
        for (int j = 0; j < array[i].Length - 1; j++)
        {
            if (char.ToLower(array[i][j]) == char.ToLower(array[i][j + 1]))
            {
                doubleLetter.Add(array[i]);
                break;
            }
        }
    }
    return doubleLetter;
}
\$\endgroup\$
0

4 Answers 4

5
\$\begingroup\$
  • The outer for loop can be replaced with a foreach loop: foreach (var name in names). It removes the need for two counter variables, and simplifies indexing of the array, making the code easier to read.
  • This method would be more flexible if it accepted a single string and returned a boolean: bool HasRepeatingLetters(string str). That allows you to use it for single names as well as for multiple names.
  • For multiple names, the above method can easily be combined with Linq: var matchingNames = names.Where(name => HasRepeatingLetters(name)).ToArray() (you can remove the ToArray (or ToList) call if you want lazy evaluation). In this case, you don't even need an anonymous function, because the signature of HasRepeatingLetters already matches what Where requires: names.Where(HasRepeatingLetters).
  • Keep in mind that ToLower is culture-dependent (not all languages use the same upper/lowercase conversion rules). You may want to give your function an extra (optional) CultureInfo argument to control its behavior.
  • Performance of your function should be O(n), not O(n^2). Passing in twice as many strings, or strings that are twice as long, requires twice as much work, not four times as much. It would only be O(n^2) if, for example, you compared each string against every other string.
  • Calling ToLower on the given string would simplify your code, and it should be a bit faster too for names without repeating characters. You could also keep your for loop, but store the previous lower-cased character as you go, so you don't need to convert it to lower-case twice. That would make the code a little more complicated, so it's probably not worth the hassle. Of course, if performance is important, you should actually measure it.
\$\endgroup\$
6
  • \$\begingroup\$ ToLower can have problems with Turkish letters. Would be better to use ToUpper. \$\endgroup\$
    – Rick Davin
    Commented Aug 2, 2017 at 21:05
  • \$\begingroup\$ @RickDavin: if you're working with Turkish names you should use a Turkish CultureInfo, otherwise both ToLower and ToUpper are going to give incorrect results (but for different characters). \$\endgroup\$ Commented Aug 2, 2017 at 21:33
  • \$\begingroup\$ The problem is that "ii" in Turkish are surrogate pairs and treated as one character. Converting to "II" is safer route. \$\endgroup\$
    – Rick Davin
    Commented Aug 2, 2017 at 21:40
  • \$\begingroup\$ @RickDavin: I'm not sure I understand what you mean. Could you provide an example where ToLower fails but ToUpper works? \$\endgroup\$ Commented Aug 2, 2017 at 21:56
  • \$\begingroup\$ foreach is slower than for \$\endgroup\$
    – paparazzo
    Commented Aug 3, 2017 at 0:20
2
\$\begingroup\$

Here is a LINQ version using Zip.

Enumerate over each character in a word and compares adjacent characters by offsetting, one enumeration, by one character, using 'Skip(1)'.
Pair characters with 'Zip'.
A match on 'Any' pair confirms.

var doubleLetters =
    array
    .Where(word => word.Zip(
                       word.Skip(1),
                       (ch1, ch2) => char.ToUpper(ch1) == char.ToUpper(ch2))
                   .Any(
                       match => match))
    .ToList();
\$\endgroup\$
1
  • \$\begingroup\$ ToCharArray() is not necessary. A string is already a char-array. \$\endgroup\$
    – t3chb0t
    Commented Aug 5, 2017 at 7:19
1
\$\begingroup\$

I was able to find a solution to my question through the use of lovely, lovely regular expressions (and LINQ, conveniently enough)!

I was able to extract the names Terry, Bill, Aaron, and Debby using the below line of code:

string[] newArray = array.Where(x => new Regex(@"((?i)[a-z\d])\1").IsMatch(x)).ToArray();

...where

  • (?i) - Ignore case of letter in the name
  • (a-z\d) - Look for any letter of the alphabet
  • \1 - Repeat search of (a-z\d) group

Still not too sure about time complexity, though. Regex time complexity eludes me :-P

\$\endgroup\$
4
  • 6
    \$\begingroup\$ Using of Regex is a good solution, but: 1) use \w instead of [a-z\d] since \w includes digits too and works for non-English letters; 2) move creation of Regex out of the Where, there is no need to create the same object multiple times. And finally: your regex doesn't work. I've checked it for "Aaron" and IsMatch returned false. The correct regular expression is new Regex(@"(\w)\1", RegexOptions.IgnoreCase). \$\endgroup\$
    – Maxim
    Commented Aug 3, 2017 at 4:15
  • \$\begingroup\$ Hmm...I thought you could use (?i) instead of RegexOptions.IgnoreCase for case-insensitivity. \$\endgroup\$
    – Delfino
    Commented Aug 3, 2017 at 12:48
  • \$\begingroup\$ Doesn't seem that I'm using (?i) correctly. I suppose I was too eager to answer my own question :-P \$\endgroup\$
    – Delfino
    Commented Aug 3, 2017 at 13:03
  • 2
    \$\begingroup\$ You can but you need to place (?i) at the start of regex pattern in your case. new Regex(@"(?i)(\w)\1") will work. But I prefer to use RegexOptions. \$\endgroup\$
    – Maxim
    Commented Aug 3, 2017 at 13:05
0
\$\begingroup\$

For a while I thought you code was broken but I had a bad test

I think this would work but not much different than your
I only wrote it because I thought your was broken

public static List<string> DoubleLetters2(string[] array)
{
    List<string> doubleLetter = new List<string>();
    foreach(string s in array)
    {
        if (DoubleLettersHelper(s))
        {
            doubleLetter.Add(s);
        }
    }
    return doubleLetter;
}
public static bool DoubleLettersHelper(string array)
{
    string lower = array.ToLower();
    for (int i = 0; i < lower.Length-1; i++)
    {
        if (lower[i] == lower[i + 1])
        {
            return true;
        }
    }
    return false;
}
\$\endgroup\$
3
  • \$\begingroup\$ Are you sure about this? The OP's code really is only comparing adjacent characters, and doesn't return "Teryry" when I test it. \$\endgroup\$ Commented Aug 3, 2017 at 19:56
  • \$\begingroup\$ @PieterWitvoet I just tested again and it does not return for me. \$\endgroup\$
    – paparazzo
    Commented Aug 3, 2017 at 20:03
  • \$\begingroup\$ @PieterWitvoet It works. I had a bad test. \$\endgroup\$
    – paparazzo
    Commented Aug 3, 2017 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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