I was prompted to give someone advice about the following problem:
Given a string with equal amount of vowels and consonants, re-arrange it so that it follows the sequence { consonant, vowel, consonant, vowel, ... }
For Example given "abed" modify it to be "bade". The order of the vowels and consonants must be the same, "dabe" nor "beda" are acceptable answers.
It was a "first year" type question, no std::string, no strlen, no copying the characters somewhere else, ...
Anyway, I came up with this. Basically, while iterating through the string, if the character isn't what we're looking for, move another pointer forward until it finds one. Once found, store it and then shift each character one to the right to make space for the character that we want:
#include <iostream>
bool isVowel( const char ch )
{
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}
void rearange( char *str )
{
bool on_consonant = true;
while ( *str )
{
bool is_vowel = isVowel( *str );
if ( ( on_consonant && is_vowel ) || ( !on_consonant && !is_vowel ) )
{
char *ptr = str + 1; // we don't get here with a valid string
while ( isVowel( *ptr ) == is_vowel )
++ptr;
// ptr now points to the first type we are looking for
char swap = *ptr;
// move each character up the line
while ( ptr != str )
{
*ptr = *( ptr - 1 );
--ptr;
}
*str = swap;
}
++str;
on_consonant = !on_consonant;
}
}
int main( int argc, char *argv[] )
{
if ( argc != 2 )
{
std::cout << "please enter a valid string as an argument\n";
return 0;
}
std::cout << argv[1] << '\n';
rearange( argv[1] );
std::cout << argv[1] << '\n';
return 0;
}
I realize that the \$O\$ notation of this isn't very good, we are going to be going back and forth across this string many times. I really couldn't think of a better way to do it with the constraints that were given. I was trying to do it in linear time, but the problem is that you never know how far forward the correct character will be and it is possible to overwrite data that hasn't even been looked at.
I offered another solution, which I do believe is linear \$( 2 * n )\$, using no constraints.
void rearange( std::string& str )
{
std::vector< char > vowels( str.length() / 2 );
std::vector< char > consonents( str.length() / 2 );
size_t v_idx = 0;
size_t c_idx = 0;
for ( char ch : str )
isVowel( ch ) ? vowels[ v_idx++ ] = ch : consonents[ c_idx++ ] = ch ;
str.clear();
for ( size_t i = 0; i < consonents.size(); ++i )
{
str += consonents[i];
str += vowels[i];
}
}
Am I correct that this is a linear operation? Are there any other ideas that could speed this up? ( Though, I'm not too worried about it, it currently takes twice as long to even make the random string ).
