Every problem has a solution

Another week, another slog post. Unfortunately I skipped last week due to an excessive amount of work, but since this week is a long weekend, I can afford to type up a post. First thing is first: the solution to last post's monkey words problem. I'm gonna paste it as it is in C# primarily because I'm lazy, but also because it adds some challenge and diversity. And also braces.

//Rules
//MW = AW
//MW = AW + "N" + MW

//AW = "A"
//AW = B + MW + S


//Verification algorithm 2 (New and improved)

private static bool IsMonkeyWord(string word)
{
    if (IsAWord(word)) //MW = AW
        return true;

    if (word.Contains('N'))
    {  
        for (int i = 0; i < word.Length; i++)
        {
            string first = "";
            string last = "";

            // Go through each n and test if everything before it is AWord and everything after is MonkeyWord
            if (word[i] == 'N') 
            {
                first = word.Substring(0, i);
                last = word.Substring(i + 1);
                if (IsAWord(first) && IsMonkeyWord(last)) //MW = AW + 'N' + MW
                    return true;
            }
        }
        return false;  
    }
    return false;
}

private static bool IsAWord(string word)
{
    //Check for null or empty
    if (word == "" || word == null) 
        return false;

    // AW = 'A'
    if (word == "A") 
        return true;

    //AW = 'B' + MW + 'S'
    if (word[0] == 'B' && word[word.Length - 1] == 'S')
        return (IsMonkeyWord(word.Substring(1, word.Length - 2)));
    return false;
}

As you can see the solution is pretty straight forward. Two functions that recursively call each other to verify the monkey word. Its pretty much a simple implementation of the rules

As for things more relevant to the course: T2 is coming up! Seemingly there's gonna be mostly trees and traversal as well as Big-Oh stuff. I'm still not quite sure how to judge and classify the efficiency of an algorithm based solely on it's code/the algorithm itself; i.e. without timing it. Would you just go through it manually with a small data set and count how many operations it does? This doesn't seem practical to me, but then again, maybe I'm just that incompetent.

Well that concludes this relatively short post. I didn't want to put too much, again primarily because I'm lazy, but also (always a second excuse!) because the code up there adds a lot of volume and people's attention spans these days are rather short, Aren't they?

Don't forget to leave some comments/feedback below! Did you solve the monkey problem? Have a better solution then mine? Want to discuss Big-Oh? All comments are welcome!