颠倒string中单词的sorting

我有这个string s1 = "My name is XYZ" ,我想颠倒单词的顺序,这样s1 = "ZYX is name My"

我可以使用额外的数组。 我想很难,但有可能做到位(不使用额外的数据结构),时间复杂度是O(n)?

反转整个string,然后颠倒每个单词的字母。

第一次通过后,string将会是

 s1 = "ZYX si eman yM" 

在第二次传球之后

 s1 = "ZYX is name My" 

扭转string,然后在第二遍中,反转每个单词…

在C#中,完全就地没有额外的数组:

 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; } 
 Not exactly in place, but anyway: Python: >>> a = "These pretzels are making me thirsty" >>> " ".join(a.split()[::-1]) 'thirsty me making are pretzels These' 

在Smalltalk中:

 'These pretzels are making me thirsty' subStrings reduce: [:a :b| b, ' ', a] 

我知道没有人关心Smalltalk,但对我来说太美了。

没有至less一些额外的数据结构,你不能做反转。 我认为当你交换字母时,最小的结构将是一个字符作为缓冲区。 它仍然可以被认为是“到位”,但它不完全是“额外的数据结构免费”。

下面是代码实施什么比尔蜥蜴描述:

 string words = "this is a test"; // Reverse the entire string for(int i = 0; i < strlen(words) / 2; ++i) { char temp = words[i]; words[i] = words[strlen(words) - i]; words[strlen(words) - i] = temp; } // Reverse each word for(int i = 0; i < strlen(words); ++i) { int wordstart = -1; int wordend = -1; if(words[i] != ' ') { wordstart = i; for(int j = wordstart; j < strlen(words); ++j) { if(words[j] == ' ') { wordend = j - 1; break; } } if(wordend == -1) wordend = strlen(words); for(int j = wordstart ; j <= (wordend + wordstart) / 2 ; ++j) { char temp = words[j]; words[j] = words[wordend - (j - wordstart)]; words[wordend - (j - wordstart)] = temp; } i = wordend; } } 

什么语言? 如果PHP,你可以在空间上爆炸,然后将结果传递给array_reverse。

如果它不是PHP,你将不得不做一些更复杂的事情,比如:

 words = aString.split(" "); for (i = 0; i < words.length; i++) { words[i] = words[words.length-i]; } 
 public static String ReverseString(String str) { int word_length = 0; String result = ""; for (int i=0; i<str.Length; i++) { if (str[i] == ' ') { result = " " + result; word_length = 0; } else { result = result.Insert(word_length, str[i].ToString()); word_length++; } } return result; } 

这是C#代码。

 In Python... ip = "My name is XYZ" words = ip.split() words.reverse() print ' '.join(words) 

无论如何,cookamunga使用python提供了很好的内联解决scheme!

这是假设所有的单词都是由空格分隔的:

 #include <stdio.h> #include <string.h> int main() { char string[] = "What are you looking at"; int i, n = strlen(string); int tail = n-1; for(i=n-1;i>=0;i--) { if(string[i] == ' ' || i == 0) { int cursor = (i==0? i: i+1); while(cursor <= tail) printf("%c", string[cursor++]); printf(" "); tail = i-1; } } return 0; } 
 class Program { static void Main(string[] args) { string s1 =" My Name varma:; string[] arr = s1.Split(' '); Array.Reverse(arr); string str = string.Join(" ", arr); Console.WriteLine(str); Console.ReadLine(); } } 

这不是完美的,但它现在适合我。 我不知道它是否有O(n)运行时间btw(仍然在研究它^^),但它使用一个额外的数组来完成任务。

这可能不是您的问题的最佳答案,因为我使用deststring来保存反转版本,而不是replace源string中的每个单词。 问题是我使用名为buf的本地堆栈variables来复制所有单词,而我不能复制到源string中,因为如果源string是const char *types,这会导致崩溃。

但是这是我第一次写作s.th. 像这样:)好吧blablub。 这里是代码:

 #include <iostream> using namespace std; void reverse(char *des, char * const s); int main (int argc, const char * argv[]) { char* s = (char*)"reservered. rights All Saints. The 2011 (c) Copyright 11/10/11 on Pfundstein Markus by Created"; char *x = (char*)"Dogfish! White-spotted Shark, Bullhead"; printf("Before: |%s|\n", x); printf("Before: |%s|\n", s); char *d = (char*)malloc((strlen(s)+1)*sizeof(char)); char *i = (char*)malloc((strlen(x)+1)*sizeof(char)); reverse(d,s); reverse(i,x); printf("After: |%s|\n", i); printf("After: |%s|\n", d); free (i); free (d); return 0; } void reverse(char *dest, char *const s) { // create a temporary pointer if (strlen(s)==0) return; unsigned long offset = strlen(s)+1; char *buf = (char*)malloc((offset)*sizeof(char)); memset(buf, 0, offset); char *p; // iterate from end to begin and count how much words we have for (unsigned long i = offset; i != 0; i--) { p = s+i; // if we discover a whitespace we know that we have a whole word if (*p == ' ' || *p == '\0') { // we increment the counter if (*p != '\0') { // we write the word into the buffer ++p; int d = (int)(strlen(p)-strlen(buf)); strncat(buf, p, d); strcat(buf, " "); } } } // copy the last word p -= 1; int d = (int)(strlen(p)-strlen(buf)); strncat(buf, p, d); strcat(buf, "\0"); // copy stuff to destination string for (int i = 0; i < offset; ++i) { *(dest+i)=*(buf+i); } free(buf); } 

我们可以将string插入到堆栈中,当我们提取单词时,它们将以相反的顺序排列。

 void ReverseWords(char Arr[]) { std::stack<std::string> s; char *str; int length = strlen(Arr); str = new char[length+1]; std::string ReversedArr; str = strtok(Arr," "); while(str!= NULL) { s.push(str); str = strtok(NULL," "); } while(!s.empty()) { ReversedArr = s.top(); cout << " " << ReversedArr; s.pop(); } } 

这个快速程序工作..虽然不检查angular落案件。

 #include <stdio.h> #include <stdlib.h> struct node { char word[50]; struct node *next; }; struct stack { struct node *top; }; void print (struct stack *stk); void func (struct stack **stk, char *str); main() { struct stack *stk = NULL; char string[500] = "the sun is yellow and the sky is blue"; printf("\n%s\n", string); func (&stk, string); print (stk); } void func (struct stack **stk, char *str) { char *p1 = str; struct node *new = NULL, *list = NULL; int i, j; if (*stk == NULL) { *stk = (struct stack*)malloc(sizeof(struct stack)); if (*stk == NULL) printf("\n####### stack is not allocated #####\n"); (*stk)->top = NULL; } i = 0; while (*(p1+i) != '\0') { if (*(p1+i) != ' ') { new = (struct node*)malloc(sizeof(struct node)); if (new == NULL) printf("\n####### new is not allocated #####\n"); j = 0; while (*(p1+i) != ' ' && *(p1+i) != '\0') { new->word[j] = *(p1 + i); i++; j++; } new->word[j++] = ' '; new->word[j] = '\0'; new->next = (*stk)->top; (*stk)->top = new; } i++; } } void print (struct stack *stk) { struct node *tmp = stk->top; int i; while (tmp != NULL) { i = 0; while (tmp->word[i] != '\0') { printf ("%c" , tmp->word[i]); i++; } tmp = tmp->next; } printf("\n"); } 

这些答案中的大多数未能解释inputstring中的前导和/或尾随空格。 考虑一下str=" Hello world" …反转整个string和反转单个单词的简单algorithm最终会导致f(str) == "world Hello "翻转分隔符。

OP说:“我想扭转单词的顺序”,并没有提到前后空格也应该翻转! 所以,虽然已经有了很多的答案,但我会在C ++中提供一个[希望]更正确的答案:

 #include <string> #include <algorithm> void strReverseWords_inPlace(std::string &str) { const char delim = ' '; std::string::iterator w_begin, w_end; if (str.size() == 0) return; w_begin = str.begin(); w_end = str.begin(); while (w_begin != str.end()) { if (w_end == str.end() || *w_end == delim) { if (w_begin != w_end) std::reverse(w_begin, w_end); if (w_end == str.end()) break; else w_begin = ++w_end; } else { ++w_end; } } // instead of reversing str.begin() to str.end(), use two iterators that // ...represent the *logical* begin and end, ignoring leading/traling delims std::string::iterator str_begin = str.begin(), str_end = str.end(); while (str_begin != str_end && *str_begin == delim) ++str_begin; --str_end; while (str_end != str_begin && *str_end == delim) --str_end; ++str_end; std::reverse(str_begin, str_end); } 

我使用堆栈的版本:

 public class Solution { public String reverseWords(String s) { StringBuilder sb = new StringBuilder(); String ns= s.trim(); Stack<Character> reverse = new Stack<Character>(); boolean hadspace=false; //first pass for (int i=0; i< ns.length();i++){ char c = ns.charAt(i); if (c==' '){ if (!hadspace){ reverse.push(c); hadspace=true; } }else{ hadspace=false; reverse.push(c); } } Stack<Character> t = new Stack<Character>(); while (!reverse.empty()){ char temp =reverse.pop(); if(temp==' '){ //get the stack content out append to StringBuilder while (!t.empty()){ char c =t.pop(); sb.append(c); } sb.append(' '); }else{ //push to stack t.push(temp); } } while (!t.empty()){ char c =t.pop(); sb.append(c); } return sb.toString(); } } 

将每个单词作为string存储在数组中,然后从最后打印

 public void rev2() { String str = "my name is ABCD"; String A[] = str.split(" "); for (int i = A.length - 1; i >= 0; i--) { if (i != 0) { System.out.print(A[i] + " "); } else { System.out.print(A[i]); } } } 

在Python中,如果你不能使用[:: – 1]或者反向(),以下是简单的方法:

 def reverse(text): r_text = text.split(" ") res = [] for word in range(len(r_text) - 1, -1, -1): res.append(r_text[word]) return " ".join(res) print (reverse("Hello World")) >> World Hello [Finished in 0.1s] 

使用C#按给定语句的相反顺序打印单词:

  void ReverseWords(string str) { int j = 0; for (int i = (str.Length - 1); i >= 0; i--) { if (str[i] == ' ' || i == 0) { j = i == 0 ? i : i + 1; while (j < str.Length && str[j] != ' ') Console.Write(str[j++]); Console.Write(' '); } } } 

其实第一个答案是:

 words = aString.split(" "); for (i = 0; i < words.length; i++) { words[i] = words[words.length-i]; } 

因为它在上半年的循环的后半部分没有实现。 所以,我<words.length / 2会起作用,但更清晰的例子是:

 words = aString.split(" "); // make up a list i = 0; j = words.length - 1; // find the first and last elements while (i < j) { temp = words[i]; words[i] = words[j]; words[j] = temp; //ie swap the elements i++; j--; } 

注意:我不熟悉PHP语法,因为它看起来与Perl相似,所以我已经猜到了增加和减less的语法。

怎么样 …

 var words = "My name is XYZ"; var wr = String.Join( " ", words.Split(' ').Reverse().ToArray() ); 

我想这不是在线的寿。

在c中,这是你如何做,O(N)和只使用O(1)数据结构(即字符)。

 #include<stdio.h> #include<stdlib.h> main(){ char* a = malloc(1000); fscanf(stdin, "%[^\0\n]", a); int x = 0, y; while(a[x]!='\0') { if (a[x]==' ' || a[x]=='\n') { x++; } else { y=x; while(a[y]!='\0' && a[y]!=' ' && a[y]!='\n') { y++; } int z=y; while(x<y) { y--; char c=a[x];a[x]=a[y];a[y]=c; x++; } x=z; } } fprintf(stdout,a); return 0; } 

使用sscanf可以做得更简单:

 void revertWords(char *s); void revertString(char *s, int start, int n); void revertWordsInString(char *s); void revertString(char *s, int start, int end) { while(start<end) { char temp = s[start]; s[start] = s[end]; s[end]=temp; start++; end --; } } void revertWords(char *s) { int start = 0; char *temp = (char *)malloc(strlen(s) + 1); int numCharacters = 0; while(sscanf(&s[start], "%s", temp) !=EOF) { numCharacters = strlen(temp); revertString(s, start, start+numCharacters -1); start = start+numCharacters + 1; if(s[start-1] == 0) return; } free (temp); } void revertWordsInString(char *s) { revertString(s,0, strlen(s)-1); revertWords(s); } int main() { char *s= new char [strlen("abc deff gh1 jkl")+1]; strcpy(s,"abc deff gh1 jkl"); revertWordsInString(s); printf("%s",s); return 0; } 
 import java.util.Scanner; public class revString { static char[] str; public static void main(String[] args) { //Initialize string //str = new char[] { 'h', 'e', 'l', 'l', 'o', ' ', 'a', ' ', 'w', 'o', //'r', 'l', 'd' }; getInput(); // reverse entire string reverse(0, str.length - 1); // reverse the words (delimeted by space) back to normal int i = 0, j = 0; while (j < str.length) { if (str[j] == ' ' || j == str.length - 1) { int m = i; int n; //dont include space in the swap. //(special case is end of line) if (j == str.length - 1) n = j; else n = j -1; //reuse reverse reverse(m, n); i = j + 1; } j++; } displayArray(); } private static void reverse(int i, int j) { while (i < j) { char temp; temp = str[i]; str[i] = str[j]; str[j] = temp; i++; j--; } } private static void getInput() { System.out.print("Enter string to reverse: "); Scanner scan = new Scanner(System.in); str = scan.nextLine().trim().toCharArray(); } private static void displayArray() { //Print the array for (int i = 0; i < str.length; i++) { System.out.print(str[i]); } } 

}

在Java中使用额外的String(使用StringBuilder):

 public static final String reverseWordsWithAdditionalStorage(String string) { StringBuilder builder = new StringBuilder(); char c = 0; int index = 0; int last = string.length(); int length = string.length()-1; StringBuilder temp = new StringBuilder(); for (int i=length; i>=0; i--) { c = string.charAt(i); if (c == SPACE || i==0) { index = (i==0)?0:i+1; temp.append(string.substring(index, last)); if (index!=0) temp.append(c); builder.append(temp); temp.delete(0, temp.length()); last = i; } } return builder.toString(); } 

在Java中:

 public static final String reverseWordsInPlace(String string) { char[] chars = string.toCharArray(); int lengthI = 0; int lastI = 0; int lengthJ = 0; int lastJ = chars.length-1; int i = 0; char iChar = 0; char jChar = 0; while (i<chars.length && i<=lastJ) { iChar = chars[i]; if (iChar == SPACE) { lengthI = i-lastI; for (int j=lastJ; j>=i; j--) { jChar = chars[j]; if (jChar == SPACE) { lengthJ = lastJ-j; swapWords(lastI, i-1, j+1, lastJ, chars); lastJ = lastJ-lengthI-1; break; } } lastI = lastI+lengthJ+1; i = lastI; } else { i++; } } return String.valueOf(chars); } private static final void swapWords(int startA, int endA, int startB, int endB, char[] array) { int lengthA = endA-startA+1; int lengthB = endB-startB+1; int length = lengthA; if (lengthA>lengthB) length = lengthB; int indexA = 0; int indexB = 0; char c = 0; for (int i=0; i<length; i++) { indexA = startA+i; indexB = startB+i; c = array[indexB]; array[indexB] = array[indexA]; array[indexA] = c; } if (lengthB>lengthA) { length = lengthB-lengthA; int end = 0; for (int i=0; i<length; i++) { end = endB-((length-1)-i); c = array[end]; shiftRight(endA+i,end,array); array[endA+1+i] = c; } } else if (lengthA>lengthB) { length = lengthA-lengthB; for (int i=0; i<length; i++) { c = array[endA]; shiftLeft(endA,endB,array); array[endB+i] = c; } } } private static final void shiftRight(int start, int end, char[] array) { for (int i=end; i>start; i--) { array[i] = array[i-1]; } } private static final void shiftLeft(int start, int end, char[] array) { for (int i=start; i<end; i++) { array[i] = array[i+1]; } } 

这是一个C实现,它正在执行逆向插入这个词,它具有O(n)复杂性。

 char* reverse(char *str, char wordend=0) { char c; size_t len = 0; if (wordend==0) { len = strlen(str); } else { for(size_t i=0;str[i]!=wordend && str[i]!=0;i++) len = i+1; } for(size_t i=0;i<len/2;i++) { c = str[i]; str[i] = str[len-i-1]; str[len-i-1] = c; } return str; } char* inplace_reverse_words(char *w) { reverse(w); // reverse all letters first bool is_word_start = (w[0]!=0x20); for(size_t i=0;i<strlen(w);i++){ if(w[i]!=0x20 && is_word_start) { reverse(&w[i], 0x20); // reverse one word only is_word_start = false; } if (!is_word_start && w[i]==0x20) // found new word is_word_start = true; } return w; } 

c#解决scheme来翻译一个句子中的单词

 using System; class helloworld { public void ReverseString(String[] words) { int end = words.Length-1; for (int start = 0; start < end; start++) { String tempc; if (start < end ) { tempc = words[start]; words[start] = words[end]; words[end--] = tempc; } } foreach (String s1 in words) { Console.Write("{0} ",s1); } } } class reverse { static void Main() { string s= "beauty lies in the heart of the peaople"; String[] sent_char=s.Split(' '); helloworld h1 = new helloworld(); h1.ReverseString(sent_char); } } 

输出:peaople心中的美女按任意键继续。 。 。

更好的版本
检查我的博客http://bamaracoulibaly.blogspot.co.uk/2012/04/19-reverse-order-of-words-in-text.html

 public string reverseTheWords(string description) { if(!(string.IsNullOrEmpty(description)) && (description.IndexOf(" ") > 1)) { string[] words= description.Split(' '); Array.Reverse(words); foreach (string word in words) { string phrase = string.Join(" ", words); Console.WriteLine(phrase); } return phrase; } return description; } 
 public class manip{ public static char[] rev(char[] a,int left,int right) { char temp; for (int i=0;i<(right - left)/2;i++) { temp = a[i + left]; a[i + left] = a[right -i -1]; a[right -i -1] = temp; } return a; } public static void main(String[] args) throws IOException { String s= "i think this works"; char[] str = s.toCharArray(); int i=0; rev(str,i,s.length()); int j=0; while(j < str.length) { if (str[j] != ' ' && j != str.length -1) { j++; } else { if (j == (str.length -1)) { j++; } rev(str,i,j); i=j+1; j=i; } } System.out.println(str); } 

我知道有几个正确的答案。 我想到了C中的那个。 这是例外答案的执行。 时间复杂度是O(n),不用额外的string。

 #include<stdio.h> char * strRev(char *str, char tok) { int len = 0, i; char *temp = str; char swap; while(*temp != tok && *temp != '\0') { len++; temp++; } len--; for(i = 0; i < len/2; i++) { swap = str[i]; str[i] = str[len - i]; str[len - i] = swap; } // Return pointer to the next token. return str + len + 1; } int main(void) { char a[] = "Reverse this string."; char *temp = a; if (a == NULL) return -1; // Reverse whole string character by character. strRev(a, '\0'); // Reverse every word in the string again. while(1) { temp = strRev(temp, ' '); if (*temp == '\0') break; temp++; } printf("Reversed string: %s\n", a); return 0; } 

用法

 char str[50] = {0}; strcpy(str, (char*)"My name is Khan"); reverseWords(str); 

方法

 void reverseWords(char* pString){ if(NULL ==pString){ return; } int nLen = strlen(pString); reverseString(pString,nLen); char* start = pString; char* end = pString; nLen = 0; while (*end) { if(*end == ' ' ){ reverseString(start,nLen); end++; start = end; nLen = 0; continue; } nLen++; end++; } reverseString(start,nLen); printf("\n Reversed: %s",pString); } void reverseString(char* start,int nLen){ char* end = start+ nLen-1; while(nLen > 0){ char temp = *start; *start = *end; *end = temp; end--; start++; nLen-=2; } }