word break using iteration Here is my word break problem in c#

static void breakSentenceIntoWords(string input,List&lt;string&gt; validWords)
    {
        if (String.IsNullOrEmpty(input))
            throw new Exception("String cannot be empty");

        int indicator = 0;
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i &lt; input.Length; i++)
        {
            builder.Append(input[i]);
            if (validWords.Contains(builder.ToString()))
            {
                indicator += builder.ToString().Length;
                Console.Write("{0} ", builder.ToString());
                builder.Clear();
            }
        }

        if (indicator != input.Length)
        {
            Console.WriteLine("Not all words could be found");
        }
    }

    List&lt;string&gt; validwords = new List&lt;string&gt;() { "I", "like", "had", "play","to" };
        breakSentenceIntoWords("Ihadplayliketo", validwords);


I think the complexity here is O(n2) because of the for-loop and the contains method. How can I improve its efficiency ?
Here you're using the name word but from your example you're actually working with substrings. Word is a vague concept but think about this:

var validWords = new List&lt;string&gt;() { "all", "to", "get", "her" };
BreakSentenceIntoWords("alltogether", validWords);


In this case you have each word from validWords but you also have another word together which is an English word but it's not in your list. Is it correct? If you're talking about words you need to consider some kind of delimiter (spaces, for example) but don't forget that it's not true in every language (Chinese, just to mention one). In your current code you're not even handling spaces.

Also note that in your current code order matters, for the above string you will get different results with { "all", "to", "together" } and this is (probably) unwanted. There are also some other corner cases you didn't handle (see answer below for other details.) I'd suggest that even before you start writing the first line of code you put in-place a huge test set (some of them also adding some randomness, I like my tests to be deterministic but working with text I always fear I forgot something then 10/20 iterations shuffling dictionaries and strings may help me to improve my test suite.)



Let's start with few general points, regardless what I said above about words.

Method name isn't best one you can choose because you're not breaking a sentence into words but you're checking if all words in that sentence are in a list of valid words. Two methods SplitStringIntoWords() and AreAllWordsKnown() might be more appropriate.

You're throwing Exception but you can do better than that, appropriate specific exception type is more informative and will help caller to handle such errors (you may have, for example, different policies for exception handling.) In this case I'd use ArgumentException. I'd also differentiate between a null input and an empty (or blank) input (using ArgumentNullException and ArgumentException respectively.) You should also check validWords to be not-null and not empty. Something like this:

if (input == null)
    throw new ArgumentNullException(nameof(input));

if (String.IsNullOrBlank(input))
    throw new ArgumentException("Input string cannot be blank", nameof(input));

if (validWords == null)
    throw new ArgumentNullException(nameof(validWords));

if (validWords.Count == 0)
    throw new ArgumentException("Known words list is empty.", nameof(validWords));

if (validWords.Any(x =&gt; x == null))
    throw new ArgumentException("Known words can't be null.", nameof(validWords));


Second step is to make this method more generic, you do not need caller to use List&lt;string&gt; when any IEnumerable&lt;string&gt; is enough to complete your task. Just change method signature.

You're also writing to console making this method not easy to reuse. Split logic and presentation, you may use a callback parameter if you need to output something or change return type to hold all the information you need. We will see more about this later.



First performance problem comes from iteration through the input string, for each character you search validWords for a match, this can be pretty inefficient when validWords or input grow to larger numbers. A small note about word searching. Linear search is not efficient for very large dictionaries (but it may be OK for 10~20 words), ordered lists and hashtables offer a huge performace gain in search (because you won't actually need to go through the entire list performing an expensive culture aware string comparison to find a match.) Later there is more about this...



Let's split your sentence into words! .NET Framework already has a function ready to use: String.Split(). If you do not specify any delimiter then it will use whitespace characters (which are many more than space and tab). For simplicity in these examples I will omit error checking (and I won't consider punctuation) but you need to do it in your code.

static string[] SplitIntoWords(string sentence)
{
    return sentence.Split(null);
}


You might want to compare with regex implementation to determine which one performs better:

static string[] SplitIntoWords(string sentence)
{
    return Regex.Split(sentence, "\\s+");;
}


Now that you have a list of words you can determine if all of them are valid. First naive implementation (don't forget what we said above about string searching in a dictionary) may be:

static bool AreAllWordsKnown(IEnumerable&lt;string&gt; words, IEnumerable&lt;string&gt; knownWords)
{
    return words.All(x =&gt; knownWords.Contains(x));
}


Note that to extract the list of not valid words you can use:

IEnumerable&lt;string&gt; unkownWords = words.Except(knownWords);


Above code can then be rewritten as:

return words.Except(knownWords).Any() == false;


To determine the list of valid words is straightforward (it's just the intersection between words and unknownWords.)



Things are different if you're not searching for words but for substrings. In this case, to avoid ordering problems, I'd first sort input list according to word length (to prefer longer matches):

var orderedValidWords = validWords.OrderBy(x =&gt; x.Length);


In this example I'm simply using String.Length but you know it's number of UTF-16 code units, not the number of characters of the string then you may have unexpected results. If you need a true culture aware check this is little bit more complex and slow:

var orderedValidWords = validWords.OrderBy(x =&gt; new StringInfo(x).LengthInTextElements);


Note that to perform a valid encoding-aware comparison you should enumerate text elements (which are...System.String) using StringInfo methods instead of System.Char.

What is slow in your actual code? You build a string for comparison, character by character. This wastes some time but think if all known words are at least 6 characters length (average word length in English is 5.1 characters), you will perform useless expensive searches. More than that you're copying characters (possibly increasing StringBuffer internal storage) just to create a new string each time with ToString() (twice...) You  may want to experiment with a custom ordinal comparison of char[] but you should first go with String.SubString (you may light to read this SO post about SubString). In short you just keep two indices (beginning of the word and current word length) and then you do:

validWords.Contains(input.SubString(wordBeginIndex, wordLength))


This alone will vastly improve performance but you can do better (for big dictionaries) adding some logic (experiment and measure) because now dictionary is ordered then:


You can check string length:


If shorter word has 4 characters and you current word is "get" then you don't need to perform any search.
If longer word is 5 characters and your actual word is 6 then (and you're not handling this in your actual code) you should move wordBeginIndex one character forward (note that this may be tricky if you want to keep track of unknown words, to simply report there are some is straightforward.)

You do not need to go through the whole list, if your word is "banana" and your list is "apple, cider, lemon" you can stop immediately when you see "cider". Be careful because ordering both for word length and alphabetically is tricky, you may want to keep only alphabetical order for simplicity (but measure, measure, measure...)
You can perform a bisection search.


What's a very fast way to search for a string in a list? HasShet&lt;string&gt;, even the generic implementation:

var dictionary = new HashSet&lt;string&gt;(validWords);


Note however that with hash-set ordering isn't preserved then you have the above mentioned ordering problem and you have to handle it elsewhere.