Kehren Sie die Reihenfolge der Wörter (nicht der Zeichen) in einem Array von Zeichen effizient um

Question

Geben Sie anhand einer Reihe von Zeichen, die einen Wortsatz bilden, einen effizienten Algorithmus an, um die Reihenfolge der Wörter (nicht der Zeichen) darin umzukehren.

Beispiel-Ein- und Ausgabe:

>>> reverse_words("this is a string")
'string a is this'

Es sollte O(N) Zeit und O(1) Raum sein (split() und Aufschieben/Abspringen vom Stapel sind nicht erlaubt).

Das Puzzle stammt aus Hier.

Answer 1

Eine Lösung in C/C++:

void swap(char* str, int i, int j){
    char t = str[i];
    str[i] = str[j];
    str[j] = t;
}

void reverse_string(char* str, int length){
    for(int i=0; i<length/2; i++){
        swap(str, i, length-i-1);
    }
}
void reverse_words(char* str){
    int l = strlen(str);
    //Reverse string
    reverse_string(str,strlen(str));
    int p=0;
    //Find word boundaries and reverse word by word
    for(int i=0; i<l; i++){
        if(str[i] == ' '){
            reverse_string(&str[p], i-p);
            p=i+1;
        }
    }
    //Finally reverse the last word.
    reverse_string(&str[p], l-p);
}

Dies sollte zeitlich O(n) und räumlich O(1) sein.

Bearbeiten:Habe es etwas aufgeräumt.

Der erste Durchgang über die Zeichenfolge ist offensichtlich O(n/2) = O(n).Der zweite Durchgang ist O(n + kombinierte Länge aller Wörter / 2) = O(n + n/2) = O(n), was dies zu einem O(n)-Algorithmus macht.

Answer 2

Eine Zeichenfolge auf einen Stapel schieben und dann abwerfen – ist das immer noch O(1)?Im Wesentlichen ist das dasselbe wie die Verwendung von split() ...

Bedeutet O(1) nicht „in-place“?Diese Aufgabe wird einfacher, wenn wir nur Zeichenfolgen und ähnliches anhängen können, aber das verbraucht Platz ...

BEARBEITEN:Thomas Watnedal hat recht.Der folgende Algorithmus ist zeitlich O(n) und räumlich O(1):

1. String direkt umkehren (erste Iteration über String)
2. jedes (umgekehrte) Wort an Ort und Stelle umkehren (zwei weitere Iterationen über die Zeichenfolge)
   1. Finden Sie die erste Wortgrenze
   2. innerhalb dieser Wortgrenze umkehren
   3. Wiederholen Sie den Vorgang für das nächste Wort, bis Sie fertig sind

Ich denke, wir müssten beweisen, dass Schritt 2 wirklich nur O(2n) ist ...

Answer 3

#include <string>
#include <boost/next_prior.hpp>

void reverse(std::string& foo) {
    using namespace std;
    std::reverse(foo.begin(), foo.end());
    string::iterator begin = foo.begin();
    while (1) {
        string::iterator space = find(begin, foo.end(), ' ');
        std::reverse(begin, space);
        begin = boost::next(space);
        if (space == foo.end())
            break;
    }
}

Answer 4

Hier ist meine Antwort.Keine Bibliotheksaufrufe und keine temporären Datenstrukturen.

#include <stdio.h>

void reverse(char* string, int length){
    int i;
    for (i = 0; i < length/2; i++){
        string[length - 1 - i] ^= string[i] ;
        string[i] ^= string[length - 1 - i];
        string[length - 1 - i] ^= string[i];
    }   
}

int main () {
char string[] = "This is a test string";
char *ptr;
int i = 0;
int word = 0;
ptr = (char *)&string;
printf("%s\n", string);
int length=0;
while (*ptr++){
    ++length;
}
reverse(string, length);
printf("%s\n", string);

for (i=0;i<length;i++){
    if(string[i] == ' '){
       reverse(&string[word], i-word);
       word = i+1;
       }
}   
reverse(&string[word], i-word); //for last word             
printf("\n%s\n", string);
return 0;
}

Answer 5

Im Pseudocode:

reverse input string
reverse each word (you will need to find word boundaries)

Answer 6

@Daren Thomas

Implementierung Ihres Algorithmus (O(N) in der Zeit, O(1) im Raum) in D (Digital Mars):

#!/usr/bin/dmd -run
/**
 * to compile & run:
 * $ dmd -run reverse_words.d
 * to optimize:
 * $ dmd -O -inline -release reverse_words.d
 */
import std.algorithm: reverse;
import std.stdio: writeln;
import std.string: find;

void reverse_words(char[] str) {
  // reverse whole string
  reverse(str);

  // reverse each word
  for (auto i = 0; (i = find(str, " ")) != -1; str = str[i + 1..length])
    reverse(str[0..i]);

  // reverse last word
  reverse(str);
}

void main() {
  char[] str = cast(char[])("this is a string");
  writeln(str);
  reverse_words(str);
  writeln(str);
}

Ausgabe:

this is a string
string a is this

Answer 7

in Ruby

„Das ist ein String“.split.reverse.join(“ „)

Answer 8

In C:(C99)

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

void reverseString(char* string, int length)
{
    char swap;
    for (int i = 0; i < length/2; i++)
    {
        swap = string[length - 1 - i];
        string[length - 1 - i] = string[i];
        string[i] = swap;
    }   
}

int main (int argc, const char * argv[]) {
    char teststring[] = "Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.";
    printf("%s\n", teststring);
    int length = strlen(teststring);
    reverseString(teststring, length);
    int i = 0;
    while (i < length)
    {
        int wordlength = strspn(teststring + i, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz");
        reverseString(teststring + i, wordlength);
        i += wordlength + 1;
    }
    printf("%s\n", teststring);
    return 0;
}

Dies ergibt die Ausgabe:

Geben Sie bei einer Reihe von Zeichen, die einen Wortsatz bilden, einen effizienten Algorithmus an, um die Reihenfolge der Wörter (nicht die Zeichen) darin umzukehren.

. es in) Zeichen nicht (Wörter der Reihenfolge der Umkehrung zum Algorithmus effizient und Worte des Satzes eine Form, die die Zeichen von Array und gegebene Zeichen

Dies dauert bei kleinem konstantem Raum höchstens 4N Zeit.Leider werden Satzzeichen und Groß-/Kleinschreibung nicht korrekt gehandhabt.

Answer 9

O(N) im Raum und O(N) in der Zeit Lösung in Python:

def reverse_words_nosplit(str_):
  """
  >>> f = reverse_words_nosplit
  >>> f("this is a string")
  'string a is this'
  """
  iend = len(str_)
  s = ""
  while True:
    ispace = str_.rfind(" ", 0, iend)
    if ispace == -1:
      s += str_[:iend]
      break
    s += str_[ispace+1:iend]
    s += " "
    iend = ispace
  return s

Answer 10

Sie würden eine so genannte iterative rekursive Funktion verwenden, die zeitlich O(N) ist, da N Iterationen erforderlich sind (N ist die Anzahl der Wörter), und räumlich O(1), da jede Iteration ihren eigenen Zustand enthält die Funktionsargumente.

(define (reverse sentence-to-reverse)
  (reverse-iter (sentence-to-reverse ""))

(define (reverse-iter(sentence, reverse-sentence)
  (if (= 0 string-length sentence)
    reverse-sentence
    ( reverse-iter( remove-first-word(sentence), add-first-word(sentence, reverse-sentence)))

Notiz:Ich habe dies in einem Schema geschrieben, in dem ich ein absoluter Neuling bin, daher entschuldige ich mich für den Mangel an korrekter String-Manipulation.

„remove-first-word“ findet die erste Wortgrenze des Satzes, entfernt dann diesen Zeichenabschnitt (einschließlich Leerzeichen und Satzzeichen) und gibt einen neuen Satz zurück

add-first-word findet die erste Wortgrenze des Satzes, fügt dann diesen Zeichenabschnitt (einschließlich Leerzeichen und Satzzeichen) zum Umkehrsatz hinzu und gibt neue Inhalte des Umkehrsatzes zurück.

Answer 11

DIESES PROGRAMM SOLL DEN SATZ UNTER VERWENDUNG VON ZEIGERN IN „C-Sprache“ UMKEHREN. Von Vasantha Kumar & Sundaramoorthy vom KONGU ENGG COLLEGE, Erode.

NOTIZ:Der Satz muss mit enden Punkt(.)Weil das Nullzeichen am Ende des Satzes* nicht automatisch zugewiesen wird*

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

int main()
{
char *p,*s="this is good.",*t;
int i,j,a,l,count=0;

l=strlen(s);

p=&s[l-1];

t=&s[-1];
while(*t)
   {
      if(*t==' ')
     count++;
     t++;
   }
   a=count;
  while(l!=0)
   {
for(i=0;*p!=' '&&t!=p;p--,i++);
   p++;

  for(;((*p)!='.')&&(*p!=' ');p++)
    printf("%c",*p);
  printf(" ");
  if(a==count)
   {
     p=p-i-1;
     l=l-i;
   }
  else
   {
     p=p-i-2;
     l=l-i-1;
   }

count--;
  }

return 0;  
}

Answer 12

Schieben Sie jedes Wort auf einen Stapel.Nimm alle Wörter vom Stapel.

Answer 13

using System;

namespace q47407
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            string s = Console.ReadLine();
            string[] r = s.Split(' ');
            for(int i = r.Length-1 ; i >= 0; i--)
                Console.Write(r[i] + " ");
            Console.WriteLine();

        }
    }
}

bearbeiten:Ich denke, ich sollte die ganze Frage lesen ...fortfahren.

Answer 14

Effizient im Hinblick auf meine Zeit:Das Schreiben in REBOL dauerte weniger als 2 Minuten:

reverse_words: func [s [string!]] [form reverse parse s none]

Versuch es:Reverse_Words "Dies ist ein String" "String a ist das"

Answer 15

Eine C++-Lösung:

#include <string>
#include <iostream>
using namespace std;

string revwords(string in) {
    string rev;
    int wordlen = 0;
    for (int i = in.length(); i >= 0; --i) {
        if (i == 0 || iswspace(in[i-1])) {
            if (wordlen) {
                for (int j = i; wordlen--; )
                    rev.push_back(in[j++]);
                wordlen = 0;
            }
            if (i > 0)
                rev.push_back(in[i-1]);
        }
        else
            ++wordlen;
    }
    return rev;
}

int main() {
    cout << revwords("this is a sentence") << "." << endl;
    cout << revwords("  a sentence   with extra    spaces   ") << "." << endl;
    return 0;
}

Answer 16

Eine Ruby-Lösung.

# Reverse all words in string
def reverse_words(string)
  return string if string == ''

  reverse(string, 0, string.size - 1)

  bounds = next_word_bounds(string, 0)

  while bounds.all? { |b| b < string.size }
    reverse(string, bounds[:from], bounds[:to])
    bounds = next_word_bounds(string, bounds[:to] + 1)
  end

  string
end

# Reverse a single word between indices "from" and "to" in "string"
def reverse(s, from, to)
    half = (from - to) / 2 + 1

    half.times do |i|
        s[from], s[to] = s[to], s[from]
        from, to = from.next, to.next
    end

    s
end

# Find the boundaries of the next word starting at index "from"
def next_word_bounds(s, from)
  from = s.index(/\S/, from) || s.size
  to = s.index(/\s/, from + 1) || s.size

  return { from: from, to: to - 1 }
end

Answer 17

in C#, direkt, O(n) und getestet:

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 18

Dieses Problem kann mit O(n) in der Zeit und O(1) im Raum gelöst werden.Der Beispielcode sieht wie folgt aus:

    public static string reverseWords(String s)
    {

        char[] stringChar = s.ToCharArray();
        int length = stringChar.Length, tempIndex = 0;

        Swap(stringChar, 0, length - 1);

        for (int i = 0; i < length; i++)
        {
            if (i == length-1)
            {
                Swap(stringChar, tempIndex, i);
                tempIndex = i + 1;
            }
            else if (stringChar[i] == ' ')
            {
                Swap(stringChar, tempIndex, i-1);
                tempIndex = i + 1;
            }
        }

        return new String(stringChar);
    }

    private static void Swap(char[] p, int startIndex, int endIndex)
    {
        while (startIndex < endIndex)
        {
            p[startIndex] ^= p[endIndex];
            p[endIndex] ^= p[startIndex];
            p[startIndex] ^= p[endIndex];
            startIndex++;
            endIndex--;
        }
    }

Answer 19

Algorithmus:1).Kehren Sie jedes Wort der Zeichenfolge um.2).Resultierende Zeichenfolge umkehren.

public class Solution {
public String reverseWords(String p) {
   String reg=" ";
  if(p==null||p.length()==0||p.equals(""))
{
    return "";
}
String[] a=p.split("\\s+");
StringBuilder res=new StringBuilder();;
for(int i=0;i<a.length;i++)
{

    String temp=doReverseString(a[i]);
    res.append(temp);
    res.append(" ");
}
String resultant=doReverseString(res.toString());
System.out.println(res);
return resultant.toString().replaceAll("^\\s+|\\s+$", ""); 
}


public String doReverseString(String s)`{`


char str[]=s.toCharArray();
int start=0,end=s.length()-1;
while(start<end)
{
char temp=str[start];
str[start]=str[end];
str[end]=temp;
start++;
end--;
}
String a=new String(str);
return a;

}

public static void main(String[] args)
{
Solution r=new Solution();
String main=r.reverseWords("kya hua");
//System.out.println(re);
System.out.println(main);
}
}

Answer 20

Ein Einzeiler:

l="Is this as expected ??"
" ".join(each[::-1] for each in l[::-1].split())

Ausgabe:

'?? expected as this Is'

Answer 21

Der Algorithmus zur Lösung dieses Problems basiert auf einem zweistufigen Prozess. Im ersten Schritt werden die einzelnen Wörter der Zeichenfolge umgekehrt, im zweiten Schritt wird die gesamte Zeichenfolge umgekehrt.Die Implementierung des Algorithmus erfordert O(n) Zeit und O(1) Raumkomplexität.

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

      void reverseStr(char* s, int start, int end);

      int main()
      {
              char s[] = "This is test string";

              int start = 0;
              int end = 0;
              int i = 0;

              while (1) {

              if (s[i] == ' ' || s[i] == '\0')
              {
                    reverseStr(s, start, end-1);
                    start = i + 1;
                    end = start;
              }
              else{
                    end++;
              }

              if(s[i] == '\0'){
                   break;
              }
              i++;
      }

      reverseStr(s, 0, strlen(s)-1);
      printf("\n\noutput= %s\n\n", s);

      return 0;
  }

  void reverseStr(char* s, int start, int end)
  {
     char temp;
     int j = end;
     int i = start;

     for (i = start; i < j ; i++, j--) {
          temp = s[i];
          s[i] = s[j];
          s[j] = temp;
     }
 }