首页 > 笔试面试题 > 关于反转字符串(Reverse Words)的思考及三种解法

关于反转字符串(Reverse Words)的思考及三种解法

2011年9月4日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

 

早些时候在水木上看到一道面试题,于是就思考着如何去解,也就有了上篇博客的整理以及这篇文章的思考。

题:反转一个字符串句子中的单词,例如“Do or do not, there is no try.”反转后为“try. no is there not, do or Do”假设所有的单词间都是以空格分离的,将标点符号视为单词的一部分。

基于上篇文章本文提供三种方法解决该问题,第一种是Houdy博客中提到的方法,后两种方法是我在思考这个问题时想到的。其中,前两种方法都是基于Divide-and-Conquer (分治)的思想,该思想非常强大,是解决问题的一个重要的方法;第三种方法是基于非分治的思想,比分治能优化一些,较为直接,欢迎讨论。

注:以下方法在实现中所用到的函数都是源自与上一篇博文:交换两段连续(不连续)内存

方法一(分治A):

上篇文章我们提到了反转内存以及如何交换两段连续和非连续的内存,这里的分析也要基于此。个人感觉Houdy的分析很到位,循序渐进,由浅入深,他的核心思想我就直接转载了,呵呵。

从整体考虑这个问题,我们要处理的是由多个单词(单词间用空格分隔)构成的字符串,这个字符串中基本的元素就是单词和空格。首先拿几个特例来分析一下,看看有没有什么收获。

  1. 字符串中没有空格。这时候相当于字符串中只有一个单词,我们不需要进行任何操作。
  2. 字符串中有一个空格(暂且认为空格在中间)。这是反转两个单词的操作,等价于反转两块不连续的内存块的操作,这个操作上篇文章我们已经实现了
  3. 字符串中有两个空格。例如 ”Tom Jerry Mike”,我们应该怎么处理这种情况呢?结合前面两个特例的分析,我们可以马上想到一种常见的解决问题思路,即分治,也就是Houdy说的 “Divide-and-Conquer”。总体来说,我们可以将包含多于一个空格的字符串划分成三个部分:   |位于空格左边的字符串|空格|位于空格右边的字符串|

这样,我们就完成下面的处理就可以了:

  1. 对空格左边的字符串进行“反转字符串”处理
  2. 对空格右边的字符串进行“反转字符串”处理
  3. 将字符串看成一个整体,对左边的串和右边的串进行“交换两块不连续内存”处理

如果左右字符串中还包含多于一个空格,我们可以分别对他们再进行“分割”+“反转”的操作,直到字符串中的空格数量不大于1,空格数等于1时,做“交换两块不连续内存”的操作。所以,我们需要计算空格数目并记录空格的索引。

还有一个问题就是,字符串中的多个空格,我们该选用哪个空格做为分割点呢?其实,基于这个问题出发,反转字符串我们就有了两种不同的做法,一种是上面提到的基于“Binary”空格的分割方法,另一种是则我刚开始用分治来思考这个问题想到的,见分治B方法:

方法二(分治B):

核心思想就是不用中间的空格对字符串进行分割,而是总用第一个空格进行分割,还以上面的例子分析,”Tom Jerry Mike”,当我们读到第一个空格时,我们知道该空格之前一定是一个单词,是不需要进行“反转字符串”操作的,所以我们只需对右边剩下的部分进行“反转字符串”操作即可,于是我们做以下处理:

  1. 读到第一个空格,对空格右边的字符串进行“反转字符串”处理
  2. 将字符串看成一个整体,对左串和右串进行“交换两块不连续内存”处理

分析分治B分治A方法比起来,程序在编写方面分治B方法比较容易,不需要计算空格数目和记录空格的位置,不需要根据空格数目考虑那么多种情况;在效率方面,都是差不多的,都是分治递归,只是分治A方法用两个递归树,每个递归的层次能较浅一些,而分治B方法用一个递归树,递归的层次自然能深一些。

下面给出了两种方法的实现:

方法一(分治A)

01 //reverse the words of one string
02 // merge reverse
03
04 void * reverseWords(void * pMemory, const size_t memSize)
05 {
06     if(NULL == pMemory)        return pMemory;
07     if(memSize < 2)    return pMemory;
08
09     char* pByteMemory = reinterpret_cast<char*>(pMemory);
10     size_t spaceNum = 0;
11     size_t* spaceIndex = new size_t [memSize];
12
13     for(size_t i = 0; i < memSize; i++)
14     {
15         if(pByteMemory[i] == SPACESEPARATOR)
16         {
17             spaceIndex[spaceNum] = i;
18             spaceNum ++;
19         }
20     }
21
22     if(spaceNum == 0){ //do nothing;
23     }
24     else if(spaceNum == 1)
25     {
26         swapNonAdjacentMemory(pByteMemory,spaceIndex[0],memSize-spaceIndex[0]-1,memSize);
27     }else
28     {
29         size_t spaceMiddle = spaceNum/2;
30         // reverse the left block of space
31         reverseWords(pByteMemory,spaceIndex[spaceMiddle]);
32         // reverse the right block of space
33         reverseWords(pByteMemory+spaceIndex[spaceMiddle]+1,memSize-spaceIndex[spaceMiddle]-1);
34         // swap the whole block
35         swapNonAdjacentMemory(pByteMemory,spaceIndex[spaceMiddle],memSize-spaceIndex[spaceMiddle]-1,memSize);
36     }
37
38     delete [] spaceIndex;
39     return pMemory;
40 }

方法二(分治B)

01 // Reverse Words
02 // 分治B方法
03 void * reverseWords(void *pMemory, const size_t memSize)
04 {
05     if(NULL == pMemory)    return pMemory;
06     if(memSize < 2)    return pMemory;
07
08     char *pStart = static_cast<char*>(pMemory);
09     for(size_t index = 0; index < memSize; ++index)
10     {
11         if(SPACESEPARATOR == pStart[index])
12         {
13             reverseWords(pStart+index+1,memSize-index-1);
14             swapNonAdjacentMemory(pStart,index,memSize-index-1,memSize);
15             break;
16         }
17     }
18     return pMemory;
19 }
可以看出,B方法的代码量只是A方法的一半,能稍微容易理解一些。

有了上述两种方法,我们给出测试用例(该测试用例亦可用于第三种方法):

01 #include <iostream>
02 using namespace std;
03
04 #define MAXBUFFERSIZE 100
05 #define SPACESEPARATOR ' '
06
07 void main()
08 {
09     static const char* stringArr[]=
10     {
11         "",
12         "ab",
13         "ab ",
14         " ab",
15         "a b",
16         "ab cd ef",
17         "ab cd ef ",
18         " ab cd ef",
19         "aaa bbbb ccccc",
20     };
21
22     void * resultArr = malloc(MAXBUFFERSIZE); // store the test result
23     if(NULL == resultArr)    return ;
24
25     size_t arrLen = sizeof(stringArr)/sizeof(*stringArr);
26
27     // reverse words
28     for(size_t i = 0; i < arrLen; i++)
29     {
30         memset(resultArr,0,MAXBUFFERSIZE);
31         memcpy(resultArr,stringArr[i],strlen(stringArr[i]));
32         reverseWords(resultArr,strlen(stringArr[i]));
33         printf("%s\n",resultArr);
34     }
35     free(resultArr);
36 }

思考:

这道题给我最大的 启发就是,看问题要有全局观,能从“整体”上去把握、分析问题,才能将问题抽象成一个最基本的问题,然后从简单到复杂,由浅入深地去分析,便能找到问题的本质。另外,分治思想不愧为解决很多问题的“不二法则”,它的关键就在于它可以将一个较大的问题划分成一个或多个规模较小的问题,同时较小的问题容易解决,只有这样才能显露分治的神奇之处。本文算法中,最终将问题转化成“交换两段不连续内存”的问题。

方法三(非分治):

第三种方法不需要递归,不需要“交换不连续内存”,就是完全利用上篇文章提到的“反转内存”这一基本操作。

Idea:很simple的一个想法:给定一个字符串,反转一次是反的,题目要求是单词为单位,那么把单词再反转过来不就可以了么?还以先前的例子分析,”Tom Jerry Mike”,反转一次为 ”ekiM yrreJ moT”,将单词反转过来得到 ”Mike Jerry Tom”,得解。于是我们做以下处理即可:

  1. 对整个字符串做“反转内存”处理
  2. 对每个单词做“反转内存”处理
实现如下:

01 void* reverseWords(void *pMemory, const size_t memSize)
02 {
03     char* pStart = static_cast<char*>(pMemory);
04
05     // check having space or not  
06     bool isHaveSpace = false;
07     for(size_t i = 0; i < memSize; ++i)
08     {
09         if(SPACESEPARATOR == pStart[i])
10         {
11             isHaveSpace = true;
12             break;
13         }
14     }
15     if(isHaveSpace) // if have not space, only one word, then return
16     {
17         reverseMemory(pMemory,memSize);  // reverse the whole string
18         size_t index = 0, istart = 0;
19         for(; index <= memSize; ++index)  // reverse every word
20         {
21             if(SPACESEPARATOR == pStart[index] || NULL == pStart[index])
22             {
23                 reverseMemory(pStart+istart,index-istart);
24                 istart = index + 1;
25             }
26         }
27     }
28     return pMemory;
29 }

程序先检查字符串是否只有一个单词,即没有空格,如果没有空格则直接返回即可。这里将只含有一个单词和空格的字符串当做另一种情况处理,即有空格的情况。

这个题目整理下来发现仔细去思考一些问题的时候还是很有收获的,第二种方法是思考分治的时候突然想到的,发现程序写起来比常用的“二分”分割思想要容易一些。第三种方法则属于没有思想的赖皮方法了,不过能用非递归的方法很好地解决这个问题,我也就贴出来了。

以上程序均测试正确,如有问题,欢迎讨论!

  • 依水远行

    我的方法类似分治B方法,但是不太相同,我是将博主回溯的部分变为直接交换,无需回溯。方法:找到第一个空格,空格左右两部分交换,再对换到左边的那段执行字符串反转。过程中需要不断计算换到左边的那段的长度。附上代码

    void *reverseSentence(void *p, const size_t header, const size_t tail, const size_t total)
    {
    	if(total < 2)
    		return p;
    	p = swapNonAdjacentMemory(p, header, tail, total);
    	char *c = (char*)p;
    	int i=0;
    	while(*c != ' '&& i<total-header-1)
    	{
    		i++;
    		c++;
    	}
    	if(i == total-header-1)
    		return p;
    	//剩余待旋转的total为total-header-1
    	reverseSentence(p, i,total-header-i-2,total-header-1);
    	return p;
    
    }