помощь в улучшении кода и эффективности времени

Question

Я написал программу, которая меняет каждое слово в строке.Например, привет и до свидания превращается в olleh dna eybdoog.Моя программа работает, однако эффективность использования времени равна o (n ^ 2), и я, вероятно, мог бы написать меньше кода.Я пытаюсь не использовать какой-либо из string.functions () (я использовал string.length () один раз).Любые советы или предложения будут оценены.

#include <iostream>
using namespace std;
void breakString(string& me, char * otherOne, int len, int count);
void reverseString(char* s); 
 int main () {
string me=("hello and goodbye");
char * otherOne;
int len=0;
int count=0;

for (len; len<me.length()+1; len++){
    count++;
    if (me[len]=='\0') {
        otherOne=new char[count];
        len-=count-1;
        count=0;
        for (len; me[len]; len++){
            otherOne[count]=me[len];
            count++;
        }
        reverseString(otherOne);
        breakString( me, otherOne, len, count);
    }
    if (me[len]==' ' ) {
        otherOne=new char[count];
        len-=count-1;
        count=0;
for (len; me[len] != ' '; len++){
    otherOne[count]=me[len];
    count++;
}
reverseString(otherOne);
        breakString( me, otherOne, len, count);
        count=0;
        otherOne=NULL;
        delete[]otherOne;
    }

}
delete[]otherOne;
cout << me;
return 0;
}
void reverseString(char* s)  
{

int len =0;
char swap;
for (len=0; s[len] != '\0'; len++);

for ( int i=0; i<len/2; i++)
{

    swap = *(s+i);

    *(s+i)= *(s+len-i-1);

    *(s+len-i-1) = swap;


}
}


void breakString(string &me, char * otherOne, int len, int count){
len-=count;
for (count=0; otherOne[count]; count++){
    me[len]=otherOne[count];
    len++;
}
}   

Answer 1

Разве это не просто что-то вроде

#include <iostream>

using namespace std;

int main () {
string me=("hello and goodbye");
int i,j, index=0;
char tmp;

for (i=0; i<me.length()+1; i++) 
    if (me[i] == ' ' || me[i] == '\0') {
        for(j=i-1;j>index;j--,index++) {
            tmp = me[index];
            me[index] = me[j];
            me[j] =tmp;
        }           
        index = i+1;
    }

cout << me;
return 0;
}

?

Сложность равна O (n): каждое слово читается дважды (или, лучше, полтора раза):один раз, так как программа находит пробел или \ 0, тогда во вложенном слове слово меняется на обратное.index указывает на слово начальный символ.

Answer 2

Вы должны быть в состоянии сделать это со стеком между входными и выходными строками.Стек полезен для хранения текущего слова, и он делает реверс для вас тоже.Я не собираюсь писать полный код для него, но алгоритм таков:

String output = ""
char Stack stack = []
while input.not_empty:
    char c = input.get_char
    if c == ' ':
        while stack.not_empty:
            output.put_char(stack.pop)
        output.put_char(c)
    else:
        stack.push(c)
while stack.not_empty:
    output.put_char(stack.pop)
return output

Это даст вам O (n), и это довольно легко доказать:

• Каждый символ читается один раз (O (1))
• Он помещается в стек (максимум) один раз (O (1))
• Он выталкивается из стека максимум один раз(O (1))
• Написано один раз (O (1))

Итак: 4 * n * O (1), то есть O (n).

Надеюсь, это поможет!

PS: Если это домашнее задание, люди с большей вероятностью помогут вам, если вы пометите это так.