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

Question

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

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

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

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

Загадка взята из здесь.

Answer 1

Решение на 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()...

Разве O (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

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

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

Answer 6

@Дарен Томас

Реализация вашего алгоритма (O(N) во времени, O(1) в пространстве) в 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);
}

Выход:

this is a string
string a is this

Answer 7

в Рубине

"это строка".split.reverse.join(" ")

Answer 8

В С:(С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 в) символах, а не (слова Ордена обратного к алгоритму эффективно дают, слова предложения, форма, какая символы массива

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

Answer 9

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 10

Вы могли бы использовать так называемую итеративную рекурсивную функцию, которая равна 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 11

ЭТА ПРОГРАММА ПРЕДНАЗНАЧЕНА ДЛЯ ПЕРЕВЕРНЕНИЯ ПРЕДЛОЖЕНИЯ С ИСПОЛЬЗОВАНИЕМ УКАЗАТЕЛЕЙ НА «ЯЗЫКЕ C». Авторы Васанта Кумар и Сундараморти из КОЛЛЕДЖА КОНГУ ЭНГ, Эрод.

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

 #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

Поместите каждое слово в стек.Вытащите все слова из стека.

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

        }
    }
}

редактировать:думаю, стоит прочитать весь вопрос...продолжать.

Answer 14

Эффективно с точки зрения моего времени:Написание в REBOL заняло менее 2 минут:

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

Попробуйте:reverse_words "Это строка" "string a is this"

Answer 15

Решение С++:

#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

Рубиновое решение.

# 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

на C#, на месте, O(n) и проверено:

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

Эту проблему можно решить с помощью O(n) во времени и O(1) в пространстве.Пример кода выглядит, как указано ниже:

    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

Алгоритм:1). Переверните каждое слово строки.2). Обратная результирующая строка.

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

Один вкладыш:

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

Выход:

'?? expected as this Is'

Answer 21

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

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