剑指offer--面试题58.翻转字符串

题目描述

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student.“,则输出”student. a am I“。

算法分析

完整代码

#include <string.h>
//把起始地址pBegin到结束地址pEnd的字符翻转
void Reverse(char* pBegin, char* pEnd)
{
    char tmp;
    while (pBegin < pEnd)
    {
        tmp = *pBegin;
        *pBegin = *pEnd;
        *pEnd = tmp;
        pBegin++;
        pEnd--;
    }
}
//算法：把整个字符串翻转，然后再把每个单词翻转
//"I am a student."->".tneduts a ma I"->"student. a am I"
void ReverseSentence(char* pData)
{
    if (pData == NULL)
        return  ;
    int len = strlen(pData);
    //把整个字符串翻转
    Reverse(pData,pData+len-1);//'\0'不能翻转到前面,不能动

    char* pBegin = pData;
    char* pEnd = pData;

    //翻转每个单词
    while (*pBegin != '\0')
    {
        if (*pBegin == ' ')//跳过' '
        {
            pBegin++;
            pEnd++;
        }
        else if (*pEnd == ' ' || *pEnd=='\0')//不是空格开始，但结尾遇到空格，这个单词结束了
        {
            Reverse(pBegin, pEnd - 1);//空格不交换
            pBegin = pEnd;
        }
        else
            pEnd++;
    }
}

int main()
{
    char str[] = "I am a student.";
    ReverseSentence(str);
    printf("%s\n",str);

    return 0;
}

利用C++实现,代码如下:

string reverseWords(string s) {
    //原字符串反转
    reverse(s.begin(), s.end());
    //构造新字符串(新字符串+=原字符串的一个单词反转 +' ')
    string s1;
    //把每个单词再反转一次
    auto p1 = s.begin();//单词的开头
    auto p2 = s.begin();//单词的尾后
    while (p1 != s.end()) {
        while (p1!=s.end() && *p1 == ' ') //跳过前面的空格
        {
            p1++;
            p2++;
        }
        if (p1 == s.end())
            break;
        while (p2 != s.end() && *p2 != ' ')//找单词的结尾后一个    
            p2++;    
        
        string tmp(p1, p2);    
        reverse(tmp.begin(), tmp.end());    
        
        s1 += tmp;    
        s1 += ' ';    
        p1 = p2;    
    }
    //删除最后的空格    
    s1.erase(s1.end() - 1);    
    return s1;    
}

本篇完！