Home
Reverse String in C/C++ (String Reversal Algorithm)
Tags:, , ,

Reverse String in C/C++ (String Reversal Algorithm)

June 28, 2014 No Comments algorithms, c / c++, string

Almost every programmer needs to write a function to reverse a given string and this exercise is kinda a favourite question in first round interviews. To reverse a string, e.g., the source string is abcd and the output string should be dcba. This article will present a few piece of C/C++ functions that illustrate different approaches to do this task.

Naive Approach

There is almost a naive solution for each tasks, and of course, it is not the optimal. But I present it here just for the comparisons to the solutions later.

The naive approach is straightforward, the idea is to allocate a new string that is size of the source string and copy to the destination in the reverse order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

char *Reverse(char *s)
{
    // point q to the last character
    char *q = s ;
    while(*q++) ;
    q -= 2 ; 
    // destination string
    char *p = new char[sizeof(char) * (q - s + 2)] ; 
    char *r = p ;
    // copy in reverse order
    while(q >= s)
        *p++ = *q-- ;
    *p = '\0' ;
    return r ;
}
char *Reverse(char *s)
{
    // point q to the last character
    char *q = s ;
    while(*q++) ;
    q -= 2 ; 
    // destination string
    char *p = new char[sizeof(char) * (q - s + 2)] ; 
    char *r = p ;
    // copy in reverse order
    while(q >= s)
        *p++ = *q-- ;
    *p = '\0' ;
    return r ;
}

In-place Reverse

The in-place reverse is an additional requirement, meaning that you are not allowed to allocate new space for destination string (like the above). The most commonly approach is each time swapping two characters, for example, for string abcdef the in-place reverse algorithm is to swap a/f, b/e, and c/d.

Give two pointers, pointing to beginning and end of the string, swapping characters pointed by each pointer, moving both pointers towards the mid until they meet each other.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

char *Reverse(char *s)
{
    // p points to the beginning
    char *p = s ;
    // q points to the end
    char *q = s ;
    while(*q)
        ++q ;
    q -- ;
    // swap and move until they meet
    while(q > p)
    {
        char t = *p ;
        *p++ = *q ;
        *q-- = t ;
    }
    return s ;
}
char *Reverse(char *s)
{
    // p points to the beginning
    char *p = s ;
    // q points to the end
    char *q = s ;
    while(*q)
        ++q ;
    q -- ;
    // swap and move until they meet
    while(q > p)
    {
        char t = *p ;
        *p++ = *q ;
        *q-- = t ;
    }
    return s ;
}

We can also do this in recursion. So we have to add to parameters a range for reversing the characters. To invoke this function, use Reverse(s, 0, strlen(s));

1
2
3
4
5
6
7
8
9
10

// Recursion method to reverse string s for given range [left, right] (index)
char *Reverse( char *s, int left, int right )
{
    if(left >= right)
        return s ;
    char t = s[left] ;
    s[left] = s[right] ;
    s[right] = t ;
    Reverse(s, left + 1, right - 1) ;
}
// Recursion method to reverse string s for given range [left, right] (index)
char *Reverse( char *s, int left, int right )
{
    if(left >= right)
        return s ;
    char t = s[left] ;
    s[left] = s[right] ;
    s[right] = t ;
    Reverse(s, left + 1, right - 1) ;
}

Recursion is simple, but not efficient because of stack frames allocation required for each recursive calls. [However, not on all occasions does the compiler allocates or use stack frames for recursive calls, depending on the situation, a compiler is often allowed to perform a tail call optimization(which all boils down to using an iteration), memory, DP among others on recursive functions. There are cases where the use of recursion serves as an efficient method of traversing(say a tree in a TDRD Parsing) and the performance loss is less significant.] We can do this using iterative loop using the same idea (indexing)

1
2
3
4
5
6
7
8
9
10
11

// Iterative method to reverse string s for given range [left, right] (index)
char *Reverse( char *s, int left, int right )
{
    while( left < right )
    {
        char t = s[left] ;
        s[left++] = s[right] ;
        s[right--] = t ;
    }
    return s ;
}
// Iterative method to reverse string s for given range [left, right] (index)
char *Reverse( char *s, int left, int right )
{
    while( left < right )
    {
        char t = s[left] ;
        s[left++] = s[right] ;
        s[right--] = t ;
    }
    return s ;
}

Swapping without temporary variable

Swapping two characters (variables) normally requires a temporary variable. But it can be eliminated (but NOT recommended in general practice just in case for your interview) using, in this case, the storage of ‘\0’ or xor (possibly other operators).

Using ‘\0’ space to swap.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// only in C/C++ that supports string ending with '\0'
char* Reverse(char* s)
{
    char* r = s ;
    // point to the end
    char* p = s;
    while (*p != '\0')
        ++p ;
    // q is the last character
    char* q = p - 1;
    // swap using '\0' space
    while (q > s)
    {
        *p = *q ;
        *q-- = *s ;
        *s++ = *p ;
    }
    *p = '\0' ; // restore
    return r ;
}
// only in C/C++ that supports string ending with '\0'
char* Reverse(char* s)
{
    char* r = s ;
    // point to the end
    char* p = s;
    while (*p != '\0')
        ++p ;
    // q is the last character
    char* q = p - 1;
    // swap using '\0' space
    while (q > s)
    {
        *p = *q ;
        *q-- = *s ;
        *s++ = *p ;
    }
    *p = '\0' ; // restore
    return r ;
}

Or, we use xor to swap without a third variable.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// using XOR to swap
char* Reverse(char* s)
{
    char* r = s ;
    // p points to the end
    char* p = s;
    while (*(p + 1) != '\0')
        ++p ;
    // xor to swap 2 characters
    while (p > s)
    {
        *p = *p ^ *s ;
        *s = *p ^ *s ;
        *p = *p-- ^ *s++ ;
    }
    return r ;
}
// using XOR to swap
char* Reverse(char* s)
{
    char* r = s ;
    // p points to the end
    char* p = s;
    while (*(p + 1) != '\0')
        ++p ;
    // xor to swap 2 characters
    while (p > s)
    {
        *p = *p ^ *s ;
        *s = *p ^ *s ;
        *p = *p-- ^ *s++ ;
    }
    return r ;
}

Reverse by words

Given source string This is a sentence and the outcome is sentence a is This. To simplify this problem, the source string does not contain comma, semicolons etc.

To accomplish this task, you can first, reverse the words only, and you get sihT si a ecnetnes and the second step is to reverse the string, which returns sentence a is This

The key point here is to determine the words, which are separated by white spaces. So we have the following function to reverse characters between pointer p and q.

1
2
3
4
5
6
7
8
9
10

// Reverse characters between p and q
void ReverseWord(char* p, char* q)
{
    while(p < q)
    {
        char t = *p ;
        *p++ = *q ;
        *q-- = t ;
    }
}
// Reverse characters between p and q
void ReverseWord(char* p, char* q)
{
    while(p < q)
    {
        char t = *p ;
        *p++ = *q ;
        *q-- = t ;
    }
}

Now, with this, we can first reverse each words in the sentence and then reverse whole string as a single word.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// Reverse the sentence
char* ReverseSentence(char *s)
{
    // p and q determines a word
    char *p = s ;    // points to the beginning of the word
    char *q = s ;    // points to the end of the word or '\0'
    while(*q != '\0')
    {
        if (*q == ' ')
        {
            ReverseWord(p, q - 1) ;
            q++ ; // points to the start of next word
            p = q ;
        }
        else
            q++ ;
    }
    ReverseWord(p, q - 1) ; // reverse the last word
    ReverseWord(s, q - 1) ; // reverse the whole sentence
    return s ;
}
// Reverse the sentence
char* ReverseSentence(char *s)
{
    // p and q determines a word
    char *p = s ;    // points to the beginning of the word
    char *q = s ;    // points to the end of the word or '\0'
    while(*q != '\0')
    {
        if (*q == ' ')
        {
            ReverseWord(p, q - 1) ;
            q++ ; // points to the start of next word
            p = q ;
        }
        else
            q++ ;
    }
    ReverseWord(p, q - 1) ; // reverse the last word
    ReverseWord(s, q - 1) ; // reverse the whole sentence
    return s ;
}

Print in Reverse order

Some questions require you to print in the reverse order, without really storing the string. This is even simpler (beginners’ task)

1
2
3
4
5
6

void ReversePrint(const char* s)
{
    int len = strlen(s) ;
    for (int i = len - 1; i >= 0; --i)
        cout << s[i];
}
void ReversePrint(const char* s)
{
    int len = strlen(s) ;
    for (int i = len - 1; i >= 0; --i)
        cout << s[i];
}

Depending on the implementation of strlen, basically there are two kinds. The first is, like the string in Delphi, the length is actually a counter stored in the previous 4-byte of string pointer, and updated dynamically. The second, is, when length counter is not stored and it has to be obtained by looking up the position of ‘\0’. So, the following illustrates the idea (NOT recommended in practice again).

1
2
3
4
5
6
7
8
9
10
11
12

void ReversePrint(const char* s)
{
    const char* p = s ;
    while (*p)
        *p++ ;
    --p ; // points p to the last character
    while (p >= s)
    {
        cout << *p ;
        --p ;
    }
}
void ReversePrint(const char* s)
{
    const char* p = s ;
    while (*p)
        *p++ ;
    --p ; // points p to the last character
    while (p >= s)
    {
        cout << *p ;
        --p ;
    }
}

The recursion gives you a clearer idea.

1
2
3
4
5
6

void ReversePrint(const char* s)
{
    if(*(s + 1) != '\0')
        ReversePrint(s + 1) ;
    cout << *s ;
}
void ReversePrint(const char* s)
{
    if(*(s + 1) != '\0')
        ReversePrint(s + 1) ;
    cout << *s ;
}

See also: Reverse a Sentence (Sentence Reversal Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
1243 words
Last Post: Pointer Arithmetic in Delphi
Next Post: Integer Data Types in Delphi

The Permanent URL is: Reverse String in C/C++ (String Reversal Algorithm)

Related posts:

  1. ChatGPT Refactors/Rewrites the Code using Promise.All – Sending Requests in Parallel In one of my project, I have the following code (Node/Javascript) that invokes a few...
  2. Multithreading Testing using Pythons’ Low Level _threading Module In Python, we can use _threading to launch a thread easily using the _thread.start_new_thread procedure....
  3. Teaching Kids Programming – Algorithms of Power of Two Teaching Kids Programming: Videos on Data Structures and Algorithms Similar to Power of Three: Teaching...
  4. Teaching Kids Programming – Algorithms to Find the Pivot Integer of the First N Natural Numbers Teaching Kids Programming: Videos on Data Structures and Algorithms Given a positive integer n, find...
  5. Dynamic Programming Algorithm to Count the Exact Sum of Subsets Given a list of positive integers nums and an integer k, return the number of...
  6. GoLang Function to Check if a String is a Subsequence of Another Given two strings s and t, return true if s is a subsequence of t,...
  7. How to Implement Integer Square Root in C/C++? Question: Implement integer square root for int sqrt(int x) There are many ways to compute the...
  8. How to Reverse Vowels of a String in C/C++? Write a function to reverse only the vowels of a string. Example: Given s =...

Leave a Reply