Efficient Algorithm for Reversing Word Order in Strings

Core Algorithm Concept

The problem of reversing word order in a string can be efficiently solved using a clever two-step reversal strategy. The core idea is to first reverse the entire string, then reverse each individual word within the string. This approach achieves O(n) time complexity and requires no additional arrays or data structures, enabling true in-place operation.

Implementation Steps

The algorithm implementation consists of two main phases. The first phase involves reversing the entire string, which can be efficiently accomplished using a two-pointer technique. For example, with the string "My name is X Y Z", complete reversal yields "Z Y X si eman yM". The second phase identifies and reverses each word by traversing the string and performing reversal when encountering spaces or the end of the string.

C# Code Implementation

Below is a C# implementation based on this algorithm, demonstrating how to reverse word order without additional arrays:

static char[] ReverseAllWords(char[] in_text)
{
    int lindex = 0;
    int rindex = in_text.Length - 1;
    if (rindex > 1)
    {
        // Reverse the entire string
        in_text = ReverseString(in_text, 0, rindex);

        // Reverse each word
        for (rindex = 0; rindex <= in_text.Length; rindex++)
        {
            if (rindex == in_text.Length || in_text[rindex] == ' ')
            {
                in_text = ReverseString(in_text, lindex, rindex - 1);
                lindex = rindex + 1;
            }
        }
    }
    return in_text;
}

static char[] ReverseString(char[] intext, int lindex, int rindex)
{
    char tempc;
    while (lindex < rindex)
    {
        tempc = intext[lindex];
        intext[lindex++] = intext[rindex];
        intext[rindex--] = tempc;
    }
    return intext;
}

Time Complexity Analysis

The algorithm has a time complexity of O(n), where n is the length of the string. Reversing the entire string requires one pass through all characters, and reversing each word requires another pass, totaling 2n operations, resulting in linear time complexity. Space complexity is O(1), as only a few temporary variables are used in addition to the input array.

Advantages and Applications

The dual-reversal method offers advantages in simplicity and efficiency. Compared to approaches using extra arrays, it conserves memory, making it particularly suitable for large strings or memory-constrained environments. This algorithm has broad applications in text processing, compiler design, data parsing, and serves as a classic example in string manipulation techniques.