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

Question

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

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

Answer 1

Это можно сделать проще, используя sscanf:

void revertWords(char *s);
void revertString(char *s, int start, int n);
void revertWordsInString(char *s);

void revertString(char *s, int start, int end)
{
     while(start<end)
     {
         char temp = s[start];
         s[start] = s[end];
         s[end]=temp;
         start++;
         end --;
     }
}


void revertWords(char *s)
{
  int start = 0;

  char *temp = (char *)malloc(strlen(s) + 1);
  int numCharacters = 0;
  while(sscanf(&s[start], "%s", temp) !=EOF)
  {
      numCharacters = strlen(temp);

      revertString(s, start, start+numCharacters -1);
      start = start+numCharacters + 1;
      if(s[start-1] == 0)
      return;

  }
  free (temp);

}

void revertWordsInString(char *s)
{
   revertString(s,0, strlen(s)-1);
   revertWords(s);
}

int main()
{
   char *s= new char [strlen("abc deff gh1 jkl")+1];
   strcpy(s,"abc deff gh1 jkl");
   revertWordsInString(s);
   printf("%s",s);
   return 0;
}

Answer 2

public static void main(String args[]) {
    String str = "My name is X Y Z"; // out put "Z Y X is name My"

    // split
    String[] arr = str.split(" ");
    // reverse word
    String reverse = "";
    for (int i = arr.length - 1; i >= 0; i--) {
        if(i!=0){
            reverse += arr[i]+" ";
        }else{
            reverse += arr[i];
        }
    }

    System.out.println(reverse);

}

Answer 3

public class manip{

public static char[] rev(char[] a,int left,int right) {
    char temp;
    for (int i=0;i<(right - left)/2;i++)    {
        temp = a[i + left];
        a[i + left] = a[right -i -1];
        a[right -i -1] = temp;
    }

    return a;
}
public static void main(String[] args) throws IOException {

    String s= "i think this works";
    char[] str = s.toCharArray();       
    int i=0;
    rev(str,i,s.length());
    int j=0;
    while(j < str.length) {
        if (str[j] != ' ' && j != str.length -1) {
            j++;
        } else
        {
            if (j == (str.length -1))   {
                j++;
            }
            rev(str,i,j);
            i=j+1;
            j=i;
        }
    }
    System.out.println(str);
}

Answer 4

Вот как это сделать в Excel как UDF и в VBA:

Public Function ReverseMe(textToReverse As String, _
          Optional delim As String = " ") As String

    Dim test    As String
    Dim arr     As Variant
    Dim arr2    As Variant
    Dim arrPart As Variant
    Dim cnt     As Long

    arr = Split(textToReverse, ".")
    ReDim arr2(UBound(arr))

    For Each arrPart In arr
        arr2(cnt) = StrReverse(arrPart)
        cnt = cnt + 1
    Next arrPart

    ReverseMe = StrReverse(Join(arr2, "."))

End Function

Public Sub TestMe()

    Debug.Print ReverseMe("veso.dosev.diri.rid", ".")
    Debug.Print ReverseMe("VBA is the best language")

End Sub

Answer 5

Я знаю, что есть несколько правильных ответов. Вот тот, в C, который я придумал. Это реализация исключенного ответа. Сложность по времени равна O (n), и дополнительная строка не используется.

#include<stdio.h>

char * strRev(char *str, char tok)
{
   int len = 0, i;
   char *temp = str;
   char swap;

   while(*temp != tok && *temp != '\0') {
      len++; temp++;
   }   
   len--;

   for(i = 0; i < len/2; i++) {
      swap = str[i];
      str[i] = str[len - i]; 
      str[len - i] = swap;
   }   

   // Return pointer to the next token.
   return str + len + 1;
}

int main(void)
{
   char a[] = "Reverse this string.";
   char *temp = a;

   if (a == NULL)
      return -1; 

   // Reverse whole string character by character.
   strRev(a, '\0');

   // Reverse every word in the string again.
   while(1) {
      temp = strRev(temp, ' ');
      if (*temp == '\0')
         break;

      temp++;
   }   
   printf("Reversed string: %s\n", a); 
   return 0;
}

Answer 6

Этот вопрос задается в интервью Paytm для позиции Java. Я придумаю следующее решение.

class ReverseStringWord{
public static void main(String[] args) {
    String s="My name is X Y Z";
    StringBuilder result=new StringBuilder();
    StringBuilder str=new StringBuilder();
    for(int i=0;i<s.length();i++){
        if(s.charAt(i)==' '){
            result.insert(0,str+" ");
            str.setLength(0);
        }
        else{
            str.append(s.charAt(i));
            if(i==s.length()-1){
                result.insert(0,str+" ");
            }
        }
    }
    System.out.println(result);
}}

Answer 7

Usage

char str[50] = {0};
strcpy(str, (char*)"My name is Khan");
reverseWords(str);

Метод

void reverseWords(char* pString){
    if(NULL ==pString){
        return;
    }
    int nLen     = strlen(pString);
    reverseString(pString,nLen);
    char* start  = pString;
    char* end    = pString;
    nLen         = 0;
    while (*end) {
        if(*end == ' ' ){
            reverseString(start,nLen);
            end++;
            start = end;
            nLen  = 0;
            continue;
        }
        nLen++;
        end++;
    }
    reverseString(start,nLen);
    printf("\n Reversed: %s",pString);

}


void reverseString(char* start,int nLen){
    char* end = start+ nLen-1;
    while(nLen > 0){
        char temp = *start;
        *start    = *end;
        *end      = temp;
        end--;
        start++;
        nLen-=2;
    }
}