关于算法：有效反转字符数组中单词(不是字符)的顺序

Efficiently reverse the order of the words (not characters) in an array of characters

给定一个组成单词句子的字符数组，给出一种有效的算法来反转单词(不是字符)在其中的顺序。

输入和输出示例：

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

它应该是O(N)时间和O(1)空间(split()，不允许压入/弹出堆栈)。

难题是从这里拿走的。

C / C ++中的解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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)算法。

将字符串推到堆栈上然后将其弹出-那还是O(1)吗？
本质上，这与使用split()相同。

O(1)不是就地吗？如果我们仅可以附加字符串和内容，则此任务将变得很容易，但这会占用空间...

编辑：托马斯·沃特纳达尔是正确的。以下算法在时间上是O(n)在空间上是O(1)：

原位反向字符串(字符串的第一次迭代)

就地反转每个(反转的)单词(在字符串上再进行两次迭代)

找到第一个单词的边界

在此词边界内反转

重复下一个单词直到完成

我想我们需要证明步骤2实际上只是O(2n)...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

这是我的答案。没有库调用，也没有临时数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#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
", string);
int length=0;
while (*ptr++){
++length;
}
reverse(string, length);
printf("%s
", 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("
%s
", string);
return 0;
}

在C中：(C99)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#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
", 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
", teststring);
return 0;
}

这给出了输出：

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.

.it in )characters not( words the
of order the reverse to algorithm
efficient an give ,words of sentence a
form which characters of array an
Given

这最多需要4N的时间，并且占用的空间很小。
不幸的是，它不能优雅地处理标点符号或大小写。

Python中空间的O(N)和时间的O(N)解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

您将使用所谓的迭代递归函数，它是O(N)的时间，因为它需要N(N为单词数)次迭代才能完成，而O(1)在空间中则是每次迭代都在其中保持自己的状态函数参数。

1
2
3
4
5
6
7

(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查找句子的第一个单词边界，然后获取该部分字符(包括空格和标点符号)并将其添加到反向句子中并返回新的反向句子内容。

用伪代码：

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

在Ruby中

"this is a string".split.reverse.join("")

THIS PROGRAM IS TO REVERSE THE SENTENCE USING POINTERS IN"C language" By Vasantha kumar & Sundaramoorthy from KONGU ENGG COLLEGE, Erode.

注意：句子必须以点号(。)结尾
因为NULL字符不会自动分配
句子结尾*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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;
}

@达伦·托马斯

在D(数字火星)中实现算法(时间为O(N)，时间为O(1))：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#!/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);
}

输出：

1
2
this is a string
string a is this

在C＃中就地进行O(n)测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
}

我的时间效率高：用不到2分钟的时间用REBOL编写：

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

试试看：
reverse_words"这是一个字符串"
"这是一个字符串"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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();

}
}
}

编辑：我想我应该阅读整个问题...继续。

Ruby解决方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 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

C ++解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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;
}

时间上的O(n)和空间上的O(1)可以解决此问题。示例代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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--;
}
}

一个班轮：

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

输出：

1
'?? expected as this Is'

Algorithm:
1).Reverse each word of the string.
2).Reverse resultant String.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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);
}
}

解决此问题的算法基于两步过程，第一步将反转字符串中的单个单词，然后在第二步中反转整个字符串。算法的实现将花费O(n)时间和O(1)空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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("

output= %s

", 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;
}
}

将每个单词推入堆栈。弹出所有单词。