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

Question

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

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

Answer 1

Лучшая версия
Проверьте мой блог http://bamaracoulibaly.blogspot.co.uk/2012/04/19-reverse-order-of-words-in-text.html

public string reverseTheWords(string description)
{
    if(!(string.IsNullOrEmpty(description)) && (description.IndexOf(" ") > 1))
    {
        string[] words= description.Split(' ');
        Array.Reverse(words);
        foreach (string word in words)
        {
            string phrase = string.Join(" ", words);
            Console.WriteLine(phrase);
        }
        return phrase;
    }
    return description;
}

Answer 2

В c, это то, как вы можете это сделать, O (N) и только используя O (1) структуры данных (то есть символ).

#include<stdio.h>
#include<stdlib.h>
main(){
  char* a = malloc(1000);
  fscanf(stdin, "%[^\0\n]", a);
  int x = 0, y;
  while(a[x]!='\0')
  {
    if (a[x]==' ' || a[x]=='\n')
    {
      x++;
    }
    else
    {
      y=x;
      while(a[y]!='\0' && a[y]!=' ' && a[y]!='\n')
      { 
        y++;
      }
      int z=y;
      while(x<y)
      {
        y--;
        char c=a[x];a[x]=a[y];a[y]=c; 
        x++;
      }
      x=z;
    }
  }

  fprintf(stdout,a);
  return 0;
}

Answer 3

Вот реализация C, которая выполняет инверсное слово inlace и имеет O(n) сложность.

char* reverse(char *str, char wordend=0)
{
    char c;
    size_t len = 0;
    if (wordend==0) {
        len = strlen(str);
    }
    else {
        for(size_t i=0;str[i]!=wordend && str[i]!=0;i++)
            len = i+1;
    }
            for(size_t i=0;i<len/2;i++) {
                c = str[i];
                str[i] = str[len-i-1];
                str[len-i-1] = c;
            }
    return str;
}

char* inplace_reverse_words(char *w)
{
    reverse(w); // reverse all letters first
    bool is_word_start = (w[0]!=0x20);

    for(size_t i=0;i<strlen(w);i++){
        if(w[i]!=0x20 && is_word_start) {
            reverse(&w[i], 0x20); // reverse one word only
            is_word_start = false;
        }
        if (!is_word_start && w[i]==0x20) // found new word
            is_word_start = true;
    }
    return w;
}

Answer 4

Собственно, первый ответ:

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

не работает, потому что отменяет во второй половине цикла ту работу, которую он делал в первой половине. Итак, я

words = aString.split(" "); // make up a list
i = 0; j = words.length - 1; // find the first and last elements
while (i < j) {
    temp = words[i]; words[i] = words[j]; words[j] = temp; //i.e. swap the elements
    i++; 
    j--;
}

Примечание: я не знаком с синтаксисом PHP, и я догадался о синтаксисе инкремента и декремента, поскольку он похож на Perl.

Answer 5

string = "hello world";
strrev = ""
list = [];
def splitstring(string):
    j = 0;
    for i in range(0,len(string)):
        if(string[i] == " "):
           list.append(string[j:i]);
           j = i+1;
        elif (i+1 == len(string)):
            list.append(string[j:i+1]);

splitstring(string);
for i in list:
    for j in range(len(i)-1,-1,-1):
        strrev += i[j];
    if (i != list[-1]):
        strrev+= " ";
print(list);

print(":%s:" %(strrev));

Answer 6

Один из способов сделать это - проанализировать каждое слово нашей входной строки и поместить его в стек LIFO.

После обработки всей строки мы выталкиваем каждое слово из стека одно за другим и добавляем его в объект класса StringBuffer, который, наконец, содержит обратную входную строку.

Это одно из возможных решений в Java с использованием StringTokenizer и класса Stack. Нам нужно импортировать java.util.Stack.

public String revString(String input)
{
   StringTokenizer words=new StringTokenizer(input); //Split the string into words
   Stack<String> stack= new Stack<String>();
   while(words.hasMoreTokens())
   {
      stack.push(words.nextElement().toString()); // Push each word of the string onto stack. 
   }
   StringBuilder revString=new StringBuilder();
   while(!stack.empty())
   {
       revString.append(stack.pop()+" ");// pop the top item and append it to revString 
   }
   return revString.toString();
}

Answer 7

import java.util.Scanner;

public class revString {
   static char[] str;

   public static void main(String[] args) {
    //Initialize string
    //str = new char[] { 'h', 'e', 'l', 'l', 'o', ' ', 'a', ' ', 'w', 'o',
    //'r', 'l', 'd' };
    getInput();

    // reverse entire string
    reverse(0, str.length - 1);

    // reverse the words (delimeted by space) back to normal
    int i = 0, j = 0;
    while (j < str.length) {

        if (str[j] == ' ' || j == str.length - 1) {

            int m = i;
            int n;

            //dont include space in the swap. 
            //(special case is end of line)
            if (j == str.length - 1)
                n = j;
            else
                n = j -1;


            //reuse reverse
            reverse(m, n);

            i = j + 1;

        }
        j++;
    }

    displayArray();
}

private static void reverse(int i, int j) {

    while (i < j) {

        char temp;
        temp = str[i];
        str[i] = str[j];
        str[j] = temp;

        i++;
        j--;
    }
}
private static void getInput() {
    System.out.print("Enter string to reverse: ");
    Scanner scan = new Scanner(System.in);
    str = scan.nextLine().trim().toCharArray(); 
}

private static void displayArray() {
    //Print the array
    for (int i = 0; i < str.length; i++) {
        System.out.print(str[i]);
    }
}

}

Answer 8

Это то, как вы решаете это в TCL, независимо от того, сколько пробелов, табуляций или символов новых строк (\ n) существует в вашей строке. это реальное решение для жизни и человеческое мышление. Он не считает один и только один пробел знаком нового слова.

И я думаю, что в C / C ++ и Java вы можете перевести это так же.

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

<!-- language: lang-php -->
# 1- Reverse the orignial text
set reversed [ string reverse  $all_original_text] 

# 2- split the reversed string $reversed into a list of words then loop over them
set list_of_reversed_words [split $reversed  ]

foreach reversed_words $list_of_reversed_words {

# 3- find the indices of the extremes of each reversed word in the $reversed

set word_start [ string first $reversed_words $reversed $word_start]
set word_end [ expr $word_start -1 + [string length $letter] ]

# 4- reverse the current-in-the-loop reversed word back to its normal state, e.g: 
# if i have a word "loohcs" then convert it by reversing it to "school"

set original_word [string reverse [ string range $reversed $word_start $word_end] ]

# 5- replace  the reversed word (loohcs) with the correcte one (school)

set reversed [ string replace $reversed $word_start $word_end $original_word]

# 6- set the start-of-search index to the index 
# directly after the ending of the current word

set word_start [expr $word_end +1]

# 7-continue to the next loop  
}

#print the result
puts "finally: $reversed"

Answer 9

В Java используется дополнительная строка (с StringBuilder):

public static final String reverseWordsWithAdditionalStorage(String string) {
    StringBuilder builder = new StringBuilder();

    char c = 0;
    int index = 0;
    int last = string.length();
    int length = string.length()-1;
    StringBuilder temp = new StringBuilder();
    for (int i=length; i>=0; i--) {
        c = string.charAt(i);
        if (c == SPACE || i==0) {
            index = (i==0)?0:i+1;
            temp.append(string.substring(index, last));
            if (index!=0) temp.append(c);
            builder.append(temp);
            temp.delete(0, temp.length());
            last = i;
        }
    }

    return builder.toString();
}

В Java на месте:

public static final String reverseWordsInPlace(String string) {
    char[] chars = string.toCharArray();

    int lengthI = 0;
    int lastI = 0;
    int lengthJ = 0;
    int lastJ = chars.length-1;

    int i = 0;
    char iChar = 0;
    char jChar = 0;
    while (i<chars.length && i<=lastJ) {
        iChar = chars[i];
        if (iChar == SPACE) {
            lengthI = i-lastI;
            for (int j=lastJ; j>=i; j--) {
                jChar = chars[j];
                if (jChar == SPACE) {
                    lengthJ = lastJ-j;
                    swapWords(lastI, i-1, j+1, lastJ, chars);
                    lastJ = lastJ-lengthI-1;
                    break;
                }
            }
            lastI = lastI+lengthJ+1;
            i = lastI;
        } else {
            i++;
        }
    }

    return String.valueOf(chars);
}

private static final void swapWords(int startA, int endA, int startB, int endB, char[] array) {
    int lengthA = endA-startA+1;
    int lengthB = endB-startB+1;

    int length = lengthA;
    if (lengthA>lengthB) length = lengthB;

    int indexA = 0;
    int indexB = 0;
    char c = 0;
    for (int i=0; i<length; i++) {
        indexA = startA+i;
        indexB = startB+i;

        c = array[indexB];
        array[indexB] = array[indexA];
        array[indexA] = c;
    }

    if (lengthB>lengthA) {
        length = lengthB-lengthA;
        int end = 0;
        for (int i=0; i<length; i++) {
            end = endB-((length-1)-i);
            c = array[end];
            shiftRight(endA+i,end,array);
            array[endA+1+i] = c;
        }
    } else if (lengthA>lengthB) {
        length = lengthA-lengthB;
        for (int i=0; i<length; i++) {
            c = array[endA];
            shiftLeft(endA,endB,array);
            array[endB+i] = c;
        }
    }
}

private static final void shiftRight(int start, int end, char[] array) {
    for (int i=end; i>start; i--) {
        array[i] = array[i-1];
    }
}

private static final void shiftLeft(int start, int end, char[] array) {
    for (int i=start; i<end; i++) {
        array[i] = array[i+1];
    }
}

Answer 10

public class StringReverse {

  public static void main(String[] args) {

    StringReverse sr =new StringReverse();
    String output=sr.reverse("reverse this string");

    String substring="";
    for(int i=0;i<=output.length();i++)
        {
        if(i==output.length()){
            System.out.print(sr.reverse(substring));
            substring="";
        }else if(output.charAt(i)==' ' ){
            System.out.print(sr.reverse(substring+" "));
            substring="";

        }
        if(i<output.length())
        {
        substring+=output.charAt(i);}
        }

}

public String reverse(String str){
    char[] value=str.toCharArray();
    int count=str.length();
    int n = count - 1;
    for (int j = (n-1) >> 1; j >= 0; --j) {
        char temp = value[j];
        value[j] = value[n - j];
        value[n - j] = temp;
    }
    return new String(value);
  }
}