Monthly Archives: June 2016

我所经历过的一道微软面试题

一个老工程师,一言不合就让我写白板,让我在白板上手写一个简单的正则表达式匹配,只用匹配*和?号,惭愧,当时没写对啊。不过,我做面试官的时候,对于现在的小朋友,从来不敢出超过二分查找难度的题的,省的两个人都尴尬。

BOOL MatchString(LPCWSTR source, LPCWSTR expression)
{
    if(expression == NULL)
    {
        return (source == NULL);
    }
    if(*expression == L"")
    {
        return (*source == L"");
    }
    if(*expression == L"*")
    {
        int sourceLen = lstrlen(source);
        for(int i=0; i<=sourceLen; i++)
        {
            if(MatchString(source + i,expression + 1))
                return TRUE;
        }
        return FALSE;
    }
    else if(*expression == L"?")
    {
        for(int i=0; i<2; i++)
        {
            if(MatchString(source + i,expression + 1))
                return TRUE;
        }
        return FALSE;
    }
    else
    {
        if(*source == *expression)
        {
            return MatchString(++source,++expression);
        }
        else
        {
            return FALSE;
        }
    }
}