Эффективно изменить порядок слов (не символов) в массиве символов

Question

Учитывая массив символов, который формирует предложение слов, дайте эффективный алгоритм, чтобы изменить порядок слов (не символов) в нем.

Пример ввода и вывода:

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

Это должно быть время O (N) и пространство O (1) (split() и вставлять / выталкивать из стека нельзя).

Головоломка взята у здесь .

Answer 1

Решение на 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);
}

Это должно быть O (n) во времени и O (1) в пространстве.

Редактировать: немного почистил.

Первый проход по строке, очевидно, O (n / 2) = O (n). Второй проход: O (n + объединенная длина всех слов / 2) = O (n + n / 2) = O (n), что делает его алгоритмом O (n).

Answer 2

помещая строку в стек, а затем выталкивая ее - это все еще O (1)? по сути, это то же самое, что и использование split () ...

О (1) не означает на месте? Эта задача становится легкой, если мы можем просто добавлять строки и прочее, но это использует пробел ...

РЕДАКТИРОВАТЬ : Томас Ватнедал прав. Следующий алгоритм - O (n) во времени и O (1) в пространстве:

1. обратная строка на месте (первая итерация над строкой)
2. поменять местами каждое (перевернутое) слово (еще две итерации по строке)
   1. найти границу первого слова
   2. повернуть вспять внутри границы этого слова
   3. повторить для следующего слова до конца

Полагаю, нам нужно доказать, что шаг 2 действительно только 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

Вот мой ответ. Нет библиотечных вызовов и временных структур данных.

#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

Вы бы использовали так называемую итеративную рекурсивную функцию, которая по времени равна O (N), так как для ее завершения требуется N (N - количество слов) и O (1) в пространстве, поскольку каждая итерация содержит свою собственное состояние в аргументах функции.

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

Примечание: я написал это на схеме, которую я начинающий, поэтому извиняюсь за отсутствие правильной манипуляции со строками.

remove-first-word находит первую границу слова в предложении, затем берет этот раздел символов (включая пробел и пунктуацию), удаляет его и возвращает новое предложение

add-first-word находит первую границу слова в предложении, затем берет этот раздел символов (включая пробел и пунктуацию) и добавляет его в обратное предложение и возвращает новое содержимое обратного предложения.

Answer 6

O (N) в пространстве и O (N) во времени в 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 7

В С: (С99)

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

Это дает вывод:

Учитывая массив символов, которые сформировать предложение слов, дать эффективный алгоритм, чтобы обратить порядок слов (не символов) в Это.

.it in) символы не (слова порядка обратного алгоритму эффективные слова, слова предложения сформировать какие символы массива Учитывая

Это занимает не более 4N времени с небольшим постоянным пространством. К сожалению, он не обрабатывает пунктуацию или регистр изящно.

Answer 8

@ Дарен Томас

Реализация вашего алгоритма (O (N) во времени, O (1) в пространстве) в D (Цифровой Марс):

#!/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);
}

Выход:

this is a string
string a is this

Answer 9

ЭТА ПРОГРАММА ОБРАТИТСЯ К ОТПРАВЛЕНИЮ С ИСПОЛЬЗОВАНИЕМ ПУНКТОВ НА "языке C" Васанта Кумар и Сундарамурти из KONGU ENGG COLLEGE, Erode.

ПРИМЕЧАНИЕ : предложение должно заканчиваться точкой (.) потому что NULL символ не назначается автоматически в конце предложения *

 #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 10

В псевдокоде:

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