Easy way to shift specific characters in a string in C++?

Question

If I have the string .....ZZ..ZZ..... or .Z.1.Z.23Z.4.Z55,

Is there an easy way of shifting all Zcharacters in the string one space right of the current position?

Some additional test strings are:

• .Z
• Z.
• ZZ.
• .ZZ
• Z
• ZZ
• ZZZ

I think a few of the higher voted answers to this question (including the currently accepted one) do not work on these tests.

Solution 1

Just iterate through the text and swap characters:

int main ()
{
    char text[] = "...Z.Z.Z...", temp;
    int text_len = strlen (text), i;
    for (i = text_len - 1; i >= 0; i--)
    {
        if (text[i] == 'Z')
        {
                temp = text[i+1];
                text[i+1] = text[i];
                text[i] = temp;
        }
    }
    printf ("%s\n", text);
    return 0;
}

Produces:

[~]$ gcc zshift.c && ./a.out
....Z.Z.Z..

---

There's a lot of discussion in the comments about a possible off-by-1 error in the above code. However, simple testing / stepping through is enough to show that this is not the case.

zshift "Z." -> ".Z"
zshift ".Z" -> "."
zshift "Z" -> ""

I think the behavior of "dropping" trailing Zs when shifting off the end of the string is sensible. After all, if you shift the bits of an integer, bits that end up outside the bounds of the integer are dropped.

If another behavior is desired -- for example, shifting only within the string -- the change to the algorithm is minimal:

temp = text[i+1];
if (temp == 0) continue;
text[i+1] = text[i];
text[i] = temp;

Solution 2

Building on previously posted code here. Function gets str and strlen, overwrites str. Works also with subsequent Z. Going forward for speed improvement with subsequent Z.

void move_z_right (char* str, int strlen) {
    for (unsigned int i = 0; i < strlen - 1; ++i)
    {
        if (str[i] == 'Z')
        {
            unsigned int j = i+1;
            while (str[j] == 'Z' && j < strlen - 1) ++j;
            if (j == strlen) break; // we are at the end, done
            char tmp = str[j];
            str[j] = str[i];
            str[i] = tmp;
            i = j; // continue after new Z next run
        }
    }
}

Note that John Millikin's solution is nicer to read and also correct.

Comments

[Michael Burr]

You need to give a better specification. When you say 'shift to the right' do you mean swap the 'Z' and the character to its right? Shift it and put a space (or something) in the spot where it was? What to do if the 'Z' is the last character? What is the correct output for your test strings?

[Andreas Magnusson]

Please also give the correct answer for each of the test strings. Simply stating them and that the given solutions doesn't work isn't much help.

[John Millikin]

@Martin: oh, oops, will change

[Tomek]

but what if you have 2 Z's next to each other, or 3 Z's or 4, etc and you wanted to shift each one of them?

[Tomek]

but what if you have 2 Z's next to each other, or 3 Z's or 4, etc and you wanted to shift each one of them?

[John Millikin]

@Tomek: Unless I'm misunderstanding, my code does that. Change text to "..ZZ.." or whatever, and it'll output the correct result.

[java872]

I believe the above code should do it. It'll shift the rightmost one, then the next rightmost, etc.. E.g. starting with: ZZ. Steps would results in: ZZ. Z.Z .ZZ

[Tomek]

@John: I'm sorry you were right, I was stepping through this on paper and it was not making sense, but then I saw that you were starting from the right side of the string, which is how this whole thing works. Its all better now, thanks again

[ypnos]

There is a bug in this code. ii needs to start with text_len - 2! otherwise, if Z is the last character in the string, it will be swapped with the ending '\0' character.

[1800 INFORMATION]

That's not right either because if it then ends with a 'Z', that 'Z' wouldn't get swapped.

[ypnos]

It was as I said it. The author corrected the code due to my comment. Thanks.

[1800 INFORMATION]

No he didn't, I changed it because of your comment, then changed it back. It's wrong either way

[John Millikin]

@ypnos: There is no off-by-1 error. strlen excludes the NULL terminator.

[Andreas Magnusson]

The simple test to settle the cause is of course to see what happens if the string passed into the routine is simply "Z". Of course it's not easy to decide what should happen in that case.

[Andreas Magnusson]

I'm not sure how it is meant to work, but a simple test made it clear to me that using ypnos fix to this code seems to be the correct solution as the modified string then would still be a permutation of the original. As it is now it won't be.

[ypnos]

Thank you Andreas for the peer review. It's funny that there is an obvious bug in the code, several developers look precisely at it and don't realize it.

[Andreas Magnusson]

Since the question is severely underspecified it's hard to argue what is right or wrong, but if you allow the Z:s to be shifted 'off' the string you end up with the decision to shift in something else instead (what?) or to truncate the string. To me none of these two options seems to be good ones.

[Andreas Magnusson]

> If another behavior is desired [snip] By changing the 'text_len - 1' to a text_len - 2' would solve it more neatly than adding an if(temp == 0) in the loop. If you think about it, the two actually mean the same.