I anticipate slowness in this algorithm to check for vowels

The speed of the following alorithm would be determined 开发者_高级运维by the number of words in the sentance and the number of characters in each word. I believe this is O(N^2)? or worse.

private bool CheckForNoVowels(string sentence)
{
    foreach (string word in sentence.Split(' '))
        foreach (char c in word)
            if (!vowels.Contains(c))
                return true;
}

Is there some sort of secret string.HasVowel Bill Gates is hiding from me? Is there a better, more efficient way to search for this. Thank you.

intent

I am trying to determine if the string is a company or a name, I assume if there is a word with no vowels, it is an abreviation or an acronym and that it is a company.

---

Regex.IsMatch(sentence, "[aoeui]");

---

No, it's perfectly good. It would be considered O(N) in the total number of characters in the input. I can't imagine this would be the performance bottleneck in your app - but you should use profiling to check for sure.

---

I'm not sure what its internal implementation is (it is marked with [MethodImpl(MethodImplOptions.InternalCall) and its algorithm doesn't appear to be documented) , but I would try the string.IndexOfAny method.

Reports the index of the first occurrence in this instance of any character in a specified array of Unicode characters. Return Value: The zero-based index position of the first occurrence in this instance where any character in anyOf was found; -1 if no character in anyOf was found.

Do note that:

The search for anyOf is case-sensitive. This method performs an ordinal (culture-insensitive) search, where a character is considered equivalent to another character only if their Unicode scalar value are the same. To perform a culture-sensitive search, use the CompareInfo.IndexOf method.

Example:

char[] vowels = { 'a', 'e', 'i', 'o', 'u' };
bool hasVowel = word.IndexOfAny(vowels) != -1;

---

Off-topic, I don't understand why your code is splitting the sentence into words and then looking at every character in every word for a vowel. The split doesn't really seem to accomplish anything.

---

If you want the time complexity to be determined based on the number of words in the sentence and the number of characters in each word, then you need two variables: the number of words, and the number of characters in each word. If you say W is the number of words, and N is the number of characters in the longest word, then your algorithm is O(W*N), not O(N^2).

---

Why not remove the outer foreach? The most expensive thing here appears to be the sentence.Split(' '), and eliminating that would merely cause the spaces to be checked for membership in vowels. Otherwise, this looks like an O(N) piece of code.

---

Where ^2 comes from?

Split is O(N)

foreach(word...) foreach (c) - walk through each character exactly once - O(N) for both "foreach" together.

vowels.Contains is constant (if numer of vowels never change) or O(number of vowels).

As result O(N) or O(N*number of vowels).

---

You could flatten the loop to avoid the unnecessary split and its string allocations, but at the end of the day you'll still have to check whether each character is a vowel:

private static readonly char[] _vowels = "AEIOUaeiou".ToCharArray();
private bool CheckForVowels(string sentence)
{
    return sentence.IndexOfAny(_vowels) != -1;
}

(I don't know the internal implementation of IndexOfAny. I'd imagine that it has to perform just such a loop, but chances are that it'll do it using unmanaged and/or unsafe code so will be at least as quick as anything you write yourself.)