学步园

题目：把句子"I love you baby"，倒置成"baby you love I"。

原题帖及解法：http://blog.csdn.net/lizhongkan/archive/2009/10/21/4708300.aspx

原帖的解法是用了辅助空间，这里说下我自己的解法，算法原地工作，不需要辅助的字符串。

解法分3步：

(1)判断字符是否为字母，参考库函数实现：

inline bool IsAlpha(char c)
{
    return (unsigned int)((c | 0x20) - 'a') < 26u;
}
(2)逆置指定长度的字符串

inline void Inverse(char * str, int nLen)
{
    char cTemp;

    if(nLen <= 1)
         return;

    for(int i=0; i<nLen/2; i++)
    {
         cTemp = str[i];
         str[i] = str[nLen-1-i];
         str[nLen-1-i] = cTemp;
    }
}

(3)算法实现：首先将整个字符串逆置，变成ybab ym evol I，再逐个将每个单词逆置，变成：baby my love I

void InverseStr(char * str)
{
    char * p = str;
    int nLen = strlen(str);
    int nSubLen = 0;

  

    //整体逆置
    Inverse(str, nLen);

    //单词逆置
    for(int i=0; i<=nLen; i++)
    {
        if(IsAlpha(str[i]))
       {
           nSubLen++;
       }
       else
       {
           Inverse(p, nSubLen);
           p = str + i + 1;
           nSubLen = 0;
       }
    }
}

个人感觉这样写思路更清楚一些，而且前两个工具函数都设计成inline函数，因此不存在函数调用开销问题。当然原帖的解法也是不错的，期待有人能提供更高效的算法～