Обратный порядок слов в строке

Question

У меня есть string s1 = "My name is X Y Z", и я хочу изменить порядок слов так, чтобы s1 = "Z Y X is name My".

Я могу сделать это, используя дополнительный массив. Я много думал, но возможно ли сделать это на месте (без использования дополнительных структур данных) и с временной сложностью O (n)?

Answer 1

Перевернуть всю строку, затем поменять буквы каждого отдельного слова.

После первого прохода строка будет

s1 = "Z Y X si eman yM"

и после второго прохода будет

s1 = "Z Y X is name My"

Answer 2

перевернуть строку, а затем во втором проходе перевернуть каждое слово ...

в c #, полностью на месте без дополнительных массивов:

static char[] ReverseAllWords(char[] in_text)
{
    int lindex = 0;
    int rindex = in_text.Length - 1;
    if (rindex > 1)
    {
        //reverse complete phrase
        in_text = ReverseString(in_text, 0, rindex);

        //reverse each word in resultant reversed phrase
        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;
}

Answer 3

Not exactly in place, but anyway: Python:

>>> a = "These pretzels are making me thirsty"
>>> " ".join(a.split()[::-1])
'thirsty me making are pretzels These'

Answer 4

В Smalltalk:

'These pretzels are making me thirsty' subStrings reduce: [:a :b| b, ' ', a]

Я знаю, что никто не заботится о Smalltalk, но это так прекрасно для меня.

Answer 5

Нельзя выполнить обращение, по крайней мере, без какой-либо дополнительной структуры данных. Я думаю, что самая маленькая структура будет одним символом в качестве буфера, когда вы меняете буквы. Его все еще можно считать «на месте», но это не совсем «лишенная структура данных».

Ниже приведен код, реализующий то, что описывает Билл Ящерица:

string words = "this is a test";

// Reverse the entire string
for(int i = 0; i < strlen(words) / 2; ++i) {
  char temp = words[i];
  words[i] = words[strlen(words) - i];
  words[strlen(words) - i] = temp;
}

// Reverse each word
for(int i = 0; i < strlen(words); ++i) {
  int wordstart = -1;
  int wordend = -1;
  if(words[i] != ' ') {
    wordstart = i;
    for(int j = wordstart; j < strlen(words); ++j) {
      if(words[j] == ' ') {
        wordend = j - 1;
        break;
      }
    }
    if(wordend == -1)
      wordend = strlen(words);
    for(int j = wordstart ; j <= (wordend + wordstart) / 2 ; ++j) {
      char temp = words[j];
      words[j] = words[wordend - (j - wordstart)];
      words[wordend - (j - wordstart)] = temp;
    }
    i = wordend;
  }
}

Answer 6

На каком языке? Если PHP, вы можете взорваться в пространстве, а затем передать результат в array_reverse.

Если это не PHP, вам придется сделать что-то более сложное, например:

words = aString.split(" ");
for (i = 0; i < words.length; i++) {
    words[i] = words[words.length-i];
}

Answer 7

In Python...

ip = "My name is X Y Z"
words = ip.split()
words.reverse()
print ' '.join(words)

В любом случае, cookamunga предоставила хорошее встроенное решение с использованием Python!

Answer 8

class Program
{
    static void Main(string[] args)
    {
        string s1 =" My Name varma:;
        string[] arr = s1.Split(' ');
        Array.Reverse(arr);
        string str = string.Join(" ", arr);
        Console.WriteLine(str);
        Console.ReadLine();

    }
}

Answer 9

public static String ReverseString(String str)
{
    int word_length = 0;
    String result = "";
    for (int i=0; i<str.Length; i++)
    {
        if (str[i] == ' ')
        {
            result = " " + result;
            word_length = 0;
        } else 
        {
            result = result.Insert(word_length, str[i].ToString());
            word_length++;
        }
    }
    return result;
}

Это код C #.

Answer 10

Предполагается, что все слова разделены пробелами:

#include <stdio.h>
#include <string.h>

int main()
{
    char string[] = "What are you looking at";
    int i, n = strlen(string);

    int tail = n-1;
    for(i=n-1;i>=0;i--)
    {
        if(string[i] == ' ' || i == 0)
        {
            int cursor = (i==0? i: i+1);
            while(cursor <= tail)
                printf("%c", string[cursor++]);
            printf(" ");
            tail = i-1;
        }
    }
    return 0;
}