Efficacement inverser l'ordre des mots (pas de caractères) dans un tableau de caractères

Question

Étant donné un tableau de caractères qui forme une phrase de mots, donner un algorithme efficace pour inverser l'ordre des mots (pas de caractères) en elle.

Exemple d'entrée et de sortie:

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

Il convient de O(N) en temps et O(1) espace (split() et en poussant sur / sautant hors de la pile ne sont pas autorisés).

Le puzzle est pris à partir de ici.

Answer 1

Une solution en 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);
}

Cela devrait être O(n) en temps et O(1) dans l'espace.

Edit:La nettoyer un peu.

Le premier passage sur la chaîne est évidemment O(n/2) = O(n).Le second passage est O(n + longueur combinée de tous les mots / 2) = O(n + n/2) = O(n), ce qui en fait un algorithme O(n).

Answer 2

poussant une chaîne sur une pile puis popping est que toujours O(1)?essentiellement, c'est la même que l'utilisation de split()...

Ne prend pas en O(1) signifie en place?Cette tâche devient facile si nous pouvons simplement ajouter des chaînes et des trucs, mais qui utilise de l'espace...

MODIFIER:Thomas Watnedal est droit.La suite de l'algorithme est O(n) en temps et O(1) dans l'espace:

1. inverser la chaîne en place (première itération sur la chaîne)
2. reverse chaque (inversé) word en place (deux itérations sur la chaîne)
   1. trouver la première limite de mot
   2. inverse à l'intérieur de cette limite de mot
   3. répétez l'opération pour le mot suivant jusqu'à la fin

Je suppose que nous aurions besoin de prouver que l'étape 2 est vraiment seulement O(2n)...

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

Voici ma réponse.Pas d'appels de bibliothèque et pas de temp structures de données.

#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

En pseudo-code:

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

Answer 6

@Thomas Daren

La mise en œuvre de votre algorithme en O(N) dans le temps, O(1) dans l'espace) dans 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);
}

Sortie:

this is a string
string a is this

Answer 7

en Ruby

"ceci est une chaîne".split.inverse.join(" ")

Answer 8

En 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;
}

Cela donne de sortie:

Étant donné un tableau de caractères qui former une phrase de mots, de donner une algorithme efficace pour inverser la l'ordre des mots (pas de caractères) dans c'.

.il en caractères non( les mots de la de l'ordre de l'inverse de l'algorithme de efficace de donner ,de mots d'une phrase la forme des caractères d'un tableau Compte tenu de

Ce qui prend au plus 4N temps, avec petite constante de l'espace.Malheureusement, Il ne gère pas les signes de ponctuation ou de cas gracieusement.

Answer 9

O(N) dans l'espace et le temps O(N) en temps de la solution en 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

Vous pourriez utiliser ce qui est connu comme un processus itératif en fonction récursive, qui est O(N) en temps qu'il faut N (N étant le nombre de mots) itérations pour compléter et O(1) dans l'espace comme chaque itération détient son propre état, dans les arguments de la fonction.

(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)))

Note:J'ai écrit cela dans le schéma dont je suis un novice complet, alors, toutes mes excuses pour le manque de corriger la manipulation de la chaîne.

retirez-premier-parole trouve le premier mot de la phrase, prend alors la section de caractères (incluant les espaces et la ponctuation) et l'enlève et retourne la nouvelle phrase

ajoutez-premier-parole trouve le premier mot de la phrase, prend alors la section de caractères (incluant les espaces et la ponctuation) et l'ajoute à l'inverse de la phrase et retourne un nouvel inverse peine contenu.

Answer 11

CE PROGRAMME vise À INVERSER LA PHRASE à l'AIDE de POINTEURS DANS le "langage C" Par Vasantha kumar & Sundaramoorthy de KONGU ENGG COLLÈGE, Éroder.

NOTE:La phrase doit se terminer par point(.) parce que caractère NULL n'est pas attribué automatiquement à la fin de la phrase*

 #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

Pousser chaque mot sur une pile.Pop tous les mots en dehors de la pile.

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();

        }
    }
}

edit:je suppose que je devrais lire l'ensemble de la question...transporter sur.

Answer 14

Efficace en termes de mon temps:a pris moins de 2 minutes pour écrire dans REBOL:

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

Essayez:reverse_words "ceci est une chaîne" "la ficelle est un présent"

Answer 15

C++ solution:

#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

Un Rubis solution.

# 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

en C#, au lieu de O(n), et testé:

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

Ce problème peut être résolu avec O(n) en temps et O(1) dans l'espace.L'exemple de code se présente comme indiqué ci-dessous:

    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

Algorithme:1).Reverse chaque mot de la chaîne.2).Inverser la Chaîne résultante.

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

En une seule ligne:

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

Sortie:

'?? expected as this Is'

Answer 21

L'algorithme pour résoudre ce problème est basée sur deux étapes, la première étape va inverser les mots individuels de la chaîne,puis dans la deuxième étape, inverser l'ensemble de la chaîne.La mise en œuvre de l'algorithme prendra O(n) en temps et O(1) l'espace de la complexité.

      #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;
     }
 }