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

Question

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

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

Answer 1

Самый простой способ сделать это ..

          string inputStr = "My name is X Y Z";
          string outputStr = string.Empty;
          List<string> templist1 = new List<string>();
          templist1 = inputStr.Split(' ').ToList();
           for (int i = templist1.Count- 1 ; i >= 0; i--)
          {
              if (outputStr != string.Empty)
              {
                  outputStr = outputStr + " " + templist1[i];
              }
              else
              {
                  outputStr = templist1[i];
              }
          }

           Console.WriteLine("Reverse of a String is", outputStr);

        Output:
        Z Y X is name My

Answer 2

Вот хороший твик для тех, кому понравился вопрос ... что делать, если алфавит, состоящий из замененных слов, меньше 16 символов (16, включая "пробел")? Есть много примеров для таких алфавитов: числовые символы [01234567890 .- +], буквы генома [GATC], гавайский алфавит [aeiouhklmnpv?], азбука Морзе [-.], музыкальные ноты [ABCDEFG # m] и т. д. Это позволяет кодировать символы в виде полубайтов (4 бита) и хранить два закодированных символа в одном 8-битном символе.

По-прежнему нетривиально выполнять замену слов в одном цикле, когда один курсор перемещается слева направо, а другой - справа налево. На самом деле существует 4 типа копирования слов: копирование слова со стороны левой строки вправо, со стороны правой строки слева и две эквивалентные копии, которые связаны с перекрытием чтения / записи: положение X-> X + y и X-> Xy, где y меньше длины X.

Приятная оптимизация состоит в том, что в течение первой половины цикла слова с правой стороны кодируются слева (сохраняя исходные левые значения), но затем на второй половине слова слева могут быть скопированы прямо вправо и тогда левые символы переписываются с их окончательными значениями ...

Вот код C, который принимает любой алфавит в качестве параметра:

#define WORDS_DELIMITER  ' '
#define UNMAPPED         0xFF

#define BITS_IN_NIBBLE   4
#define BITS_IN_BYTE     8
#define CHARS_IN_NIBBLE  (1 << BITS_IN_NIBBLE)
#define CHARS_IN_BYTE    (1 << BITS_IN_BYTE)

typedef union flip_char_ {
    unsigned char clear;
    struct {
        unsigned char org:4;
        unsigned char new:4;
    } encoded;
} flip_char_t;

typedef struct codec_ {
    unsigned char nibble2ascii[CHARS_IN_NIBBLE];
    unsigned char ascii2nibble[CHARS_IN_BYTE];
} codec_t;

static int 
codec_init (const unsigned char *alphabet, codec_t *codec)
{
size_t len = strlen(alphabet), i;

if (len > CHARS_IN_NIBBLE) {
    fprintf(stderr, "alphabet is too long!\n");
    return -1;
}
if (strchr(alphabet, WORDS_DELIMITER) == NULL) {
    fprintf(stderr, "missing space in the alphabet\n");
    return -1;
}
strcpy(codec->nibble2ascii, alphabet);
memset(codec->ascii2nibble , UNMAPPED, CHARS_IN_BYTE);
for (i=0; i<len; i++) {
    codec->ascii2nibble[ alphabet[i] ] = i;
}
return 0;
}

static inline int
is_legal_char (const codec_t *codec, const unsigned char ch)
{
return codec->ascii2nibble[ch] != UNMAPPED;
}

static inline unsigned char 
encode_char (const codec_t *codec, unsigned char org, unsigned char new)
{
flip_char_t flip;
flip.encoded.org = codec->ascii2nibble[org];
flip.encoded.new = codec->ascii2nibble[new];
return flip.clear;
} 

static inline unsigned char 
decode_org (const codec_t *codec, unsigned char ch)
{
flip_char_t flip = { .clear = ch };
return codec->nibble2ascii[flip.encoded.org];
}

static inline unsigned char 
decode_new (const codec_t *codec, unsigned char ch)
{
flip_char_t flip = { .clear = ch };
return codec->nibble2ascii[flip.encoded.new];
}

// static void inline
// encode_char (const char *alphabet, const char *
static int 
flip_words (const unsigned char *alphabet, unsigned char *a, size_t len)
{
codec_t codec;     /* mappings of the 16char-alphabet to a nibble */
int r=len-1;       /* right/reader cursor: moves from right to left scanning for words */
int l=0;           /* left/writer cursor: moves from left to right */
int i=0;                      /* word iterator */
int start_word=-1,end_word=-1; /* word boundaries */
unsigned char org_r=0;        /* original value pointed by the right cursor */
int encode=0, rewrite=0;      /* writing states */

if (codec_init(alphabet, &codec) < 0) return -1;

/* parse the buffer from its end backward */
while (r>=0) {
    if (r>=l && !is_legal_char(&codec, a[r])) {
        fprintf(stderr, "illegal char %c in string\n", a[r]);
        return -1;
    }
    /* read the next charachter looking for word boundaries */
    org_r = (r<l) ? decode_org(&codec, a[r]) : a[r];
    /* handle word boundaries */
    if (org_r == WORDS_DELIMITER) {
        /* mark start of word: next char after space after non-space  */ 
        if (end_word>0 && start_word<0) start_word = r/*skip this space*/+1;
        /* rewrite this space if necessary (2nd half) */
        if (r<l) a[r] = decode_new(&codec,a[r]);
    } else {
        /* mark end of word: 1st non-space char after spaces */ 
        if (end_word<0) end_word = r;
        /* left boundary is a word boundary as well */
        if (!r) start_word = r;
    }
    /* Do we have a complete word to process? */
    if (start_word<0 || end_word<0) {
        r--;
        continue;
    }
    /* copy the word into its new location */
    for(i=start_word; i<=end_word; i++, l++) {
        if (i>=l && !is_legal_char(&codec, a[l])) {
            fprintf(stderr, "illegal char %c in string\n", a[l]);
            return -1;
        }
        /* reading phase: value could be encoded or not according to writer's position */
        org_r= (i<l) ? decode_org(&codec, a[i]) : a[i];
        /* overlapping words in shift right: encode and rewrite */
        encode=rewrite=(l>=start_word && l<=end_word && i<l);
        /* 1st half - encode both org and new vals */
        encode|=(start_word-1>l);
        /* 2nd half - decode and rewrite final values */
        rewrite|=(i<l);
        /* writing phase */
        a[l]= encode ? encode_char(&codec, a[l], org_r) : org_r;
        if (rewrite) {
            a[i]=decode_new(&codec, a[i]);
        }
    }
    /* done with this word! */
    start_word=end_word=-1;
    /* write a space delimiter, unless we're at the end */
    if (r) {
        a[l] = l<r ? encode_char(&codec, a[l], WORDS_DELIMITER) : WORDS_DELIMITER;
        l++;
    }
    r--;
}
a[l]=0;
return 0; /* All Done! */
}

Answer 3

Использование Java:

String newString = "";
String a = "My name is X Y Z";
    int n = a.length();
    int k = n-1;
    int j=0;

    for (int i=n-1; i>=0; i--)
    {
        if (a.charAt(i) == ' ' || i==0)
        {

            j= (i!=0)?i+1:i;

            while(j<=k)
            {
                newString = newString + a.charAt(j);
                j=j+1;
            }
            newString = newString + " ";
            k=i-1;
        }

    }
    System.out.println(newString);

Сложность: O (n) [обход всего массива] + O (n) [повторение каждого слова] = O (n)

Answer 4

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

void reverse(char *data, int len) {
    int counter = 0;
    int end = len - 1;
    char temp;

    for (counter = 0; counter < len / 2; counter++, end--) {
        temp = data[counter];
        data[counter] = data[end];
        data[end] = temp;
    }
}

int main(void) {
    char data[] = "This is a line and needs to be reverse by words!";
    int c = 0;
    int len = strlen(data);
    int wl = 0;
    int start = 0;
    printf("\n    data =  %s", data);
    reverse(data, len);

    for (c = 0; c < len; c++) {
        if (!wl) {
            start = c;
        }
        if (data[c] != ' ') {
            wl++;
        } else {
            reverse(data + start, wl);
            wl = 0;
        }

    }

    printf("\nnow data =  %s", data);
    return EXIT_SUCCESS;
}

Answer 5

c # решение для обращения слов в предложении

using System;
class helloworld {
    public void ReverseString(String[] words) {
        int end = words.Length-1;
        for (int start = 0; start < end; start++) {
            String tempc;
            if (start < end ) {
                tempc = words[start];
                words[start] = words[end];
                words[end--] = tempc;
            }
        }
        foreach (String s1 in words) {
            Console.Write("{0} ",s1);
        }
    }
}
class reverse {
    static void Main() {
        string s= "beauty lies in the heart of the peaople";
        String[] sent_char=s.Split(' ');
        helloworld h1 = new helloworld();
        h1.ReverseString(sent_char);
    }
}

Выход: люди сердца во лжи красоты Нажмите любую клавишу, чтобы продолжить. , .

Answer 6

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ReverseString
{
    class Program
    {
        static void Main(string[] args)
        {
            string StringReverse = "";
            int StringLength;
            do
            {
                Console.WriteLine("Enter the String : ");
                string InputString = Console.ReadLine();

                Console.WriteLine("Enter the length : ");
                int InputLength = Convert.ToInt32(Console.ReadLine());

                int NewLength = InputLength;
                InputLength = InputLength - 1;
                int LengthString = InputString.Length;
                int l = LengthString - NewLength;
                StringReverse = "";

                while (InputLength >= 0)
                {
                    StringReverse = StringReverse + InputString[InputLength];
                    InputLength--;
                }

                String substr = InputString.Substring(NewLength, l);

                Console.WriteLine("Reverse  String  Is  {0}", StringReverse + substr);

                Console.WriteLine("\tDo you Want to CONTINUE?\n\t1.YES\n\t2.NO");
                StringLength = Convert.ToInt32(Console.ReadLine());
            } 
            while (StringLength == 1);
        }
    }
}

Answer 7

Вот алгоритм:

1. Разнесите строку пробелом и создайте массив слов.
2. Обратный массив.
3. взорвать массив пробелом.

Answer 8

public class reversewords {

public static void main(String args[])

{

String s="my name is nimit goyal";

    char a[]=s.toCharArray();
    int x=s.length();
    int count=0;
    for(int i=s.length()-1 ;i>-1;i--)
    { 
        if(a[i]==' ' ||i==0)
        { //System.out.print("hello");
            if(i==0)
            {System.out.print(" ");}
            for(int k=i;k<x;k++)
            {
                System.out.print(a[k]);
                count++;
            }
            x=i;

        }count++;

    }
    System.out.println("");
    System.out.println("total run =="+count);
}

}

Выход: Goyal Nimit это имя мое

общий пробег == 46

Answer 9

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

Способ, которым я реализовал -

1. Перевернуть все предложение, символ за символом.
2. Позже итерация всего предложения, но на этот раз поменяйте местами каждое слово.

И ПОЧЕМУ Я ПОЛУЧИЛ СЛОЖНОСТЬ В МИРОВОЕ ВРЕМЯ КАК О (n sqaure)

Пожалуйста, найдите код ниже в java, надеюсь, он кому-нибудь поможет.

class MainClass {
    public static void main(String args[]) {

        String str = "reverse me! also lets check";
        System.out.println("The initial string is  --->> " + str);

        for (int i = 0; i < str.length(); i++) {
            //Keep iterating each letter from one end to another.
            str = str.substring(1, str.length() - i)
                + str.substring(0, 1)
                + str.substring(str.length() - i, str.length());
        }
        System.out.println("The reversed string is ---->> " + str);

        for (int i = 0, j = 0; i < str.length(); i++) {
            if(str.charAt(i) == ' ' || i == (str.length() - 1)) {
                //Just to know the start of each word
                int k = j;

                //the below if condition is for considering the last word.
                if(i == (str.length() - 1)) i++;

                while(j < i) {
                    j++;
                    str = str.substring(0, k)
                        //(i-j) is the length of each word
                        + str.substring(k + 1, (k + 1) + i - j)
                        + str.substring(k, k + 1)
                        + str.substring((k + 1) + i - j, i)
                        + str.substring(i);
                    if(j == i) {
                        //Extra j++ for considering the empty white space
                        j++;
                    }
                }
            }
        }
        System.out.println("The reversed string but not the reversed words is ---->> " + str);

    }
}

Answer 10

В JAVA

package Test;

public class test2 {

    public static void main(String[] args){

        String str = "my name is fawad X Y Z";

        String strf = "";
        String strfinal="";

        if (str != ""){

        for (int i=0 ; i<=str.length()-1; i++){

            strf += str.charAt(str.length() - (i+1));

        }
        System.out.println(strf);
        }
        else System.out.println("String is Null");

            if (strf != ""){
                String[] temp = strf.split(" ");    

                String temp1 = "";

                System.out.println(temp.length);

                for (int j=0; j<=temp.length-1; j++){

                    temp1 = temp[j];

                    if(temp1.length()>1){

                    for (int k=0; k<=temp1.length()-1; k++){

                        strfinal += temp1.charAt(temp1.length()-(1+k));

                    }
                    strfinal += " ";
                    }
                    else strfinal += temp1 + " ";

                }
                System.out.println(strfinal);

            }
            else System.out.println("String Final is Null");
        }
    }

Выход:

Z Y X dawaf si eman ym

Z Y X fawad is name my