Kehren Sie die Reihenfolge der Wörter in einer Zeichenfolge um
Ich habe diesen string s1 = "My name is X Y Z" und ich möchte die Reihenfolge der Wörter umkehren, so dass s1 = "Z Y X is name My".
Ich kann es mit einem zusätzlichen Array tun. Ich habe nachgedacht, aber ist es möglich, dies zu tun (ohne zusätzliche Datenstrukturen zu verwenden) und die zeitliche Komplexität O (n) ist?
Kehren Sie die gesamte Zeichenfolge um und kehren Sie dann die Buchstaben jedes einzelnen Wortes um.
Nach dem ersten Durchlauf wird die Zeichenfolge sein
s1 = "Z Y X si eman yM"
und nach dem zweiten Durchgang wird es sein
s1 = "Z Y X is name My"
die Zeichenkette umkehren und dann in einem zweiten Durchlauf jedes Wort umkehren ...
in c #, vollständig in-place ohne zusätzliche Arrays:
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'
In Smalltalk:
'These pretzels are making me thirsty' subStrings reduce: [:a :b| b, ' ', a]
Ich weiß, dass sich niemand für Small Talk interessiert, aber es ist für mich so schön.
Sie können die Stornierung nicht ohne mindestens eine zusätzliche Datenstruktur durchführen. Ich denke, die kleinste Struktur wäre ein einzelnes Zeichen als Puffer, während Sie Buchstaben austauschen. Es kann immer noch als "in situ" betrachtet werden, aber es ist nicht vollständig "zusätzliche Datenstruktur frei".
Im Folgenden wird der Code implementiert, der das, was Bill the Lizard beschreibt, implementiert:
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;
}
}
Welche Sprache? Wenn PHP explodiert, können Sie das Ergebnis an array_reverse übergeben.
Wenn es nicht PHP ist, müssen Sie etwas komplexeres tun, wie:
words = aString.split(" ");
for (i = 0; i < words.length; i++) {
words[i] = words[words.length-i];
}
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();
}
}
Dies setzt voraus, dass alle Wörter durch Leerzeichen getrennt sind:
#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;
}
In Python...
ip = "My name is X Y Z"
words = ip.split()
words.reverse()
print ' '.join(words)
Trotzdem bot cookamunga eine gute Inline-Lösung mit Python!
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;
}
Dies ist C # -Code.
Das ist nicht perfekt, aber es funktioniert jetzt für mich. Ich weiß nicht, ob es O(n) zur Laufzeit hat (studiert es noch ^^), aber es verwendet ein zusätzliches Array, um die Aufgabe zu erfüllen.
Es ist wahrscheinlich nicht die beste Antwort auf Ihr Problem, weil ich die umgekehrte Version mit einem Zielstring speichere, anstatt jedes Wort im Quellstring zu ersetzen. Das Problem ist, dass ich eine lokale Stapelvariable namens buf verwende, um alle Wörter in zu kopieren, und ich kann nicht in den Quellstring kopieren, da dies zu einem Absturz führen würde, wenn der Quellstring const char * type ist.
Aber es war mein erster Versuch, an s.th zu schreiben. so :) :) Ok genug blablub. hier ist code:
#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);
}
Wenn Sie in Python [:: - 1] oder reversed () nicht verwenden können, gehen Sie folgendermaßen vor:
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]
Meine Version von Stack:
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();
}
}
Die meisten dieser Antworten berücksichtigen keine führenden und/oder nachgestellten Leerzeichen in der Eingabezeichenfolge. Betrachten Sie den Fall von str=" Hello world"... Der einfache Weg, die gesamte Zeichenfolge umzukehren und einzelne Wörter umzukehren, führt zu einer Umkehrung der Trennzeichen, die zu f(str) == "world Hello " führt.
Das OP sagte "Ich möchte die Reihenfolge der Wörter umkehren" und erwähnte nicht, dass führende und nachgestellte Leerzeichen auch umgedreht werden sollten! Obwohl es schon eine Menge Antworten gibt, werde ich in C++ eine [hoffentlich] korrektere Antwort geben:
#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);
}
Wir können die Zeichenfolge in einen Stapel einfügen und wenn wir die Wörter extrahieren, werden sie in umgekehrter Reihenfolge sein.
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();
}
}
Hier ist die Java-Implementierung:
public static String reverseAllWords(String given_string)
{
if(given_string == null || given_string.isBlank())
return given_string;
char[] str = given_string.toCharArray();
int start = 0;
// Reverse the entire string
reverseString(str, start, given_string.length() - 1);
// Reverse the letters of each individual Word
for(int end = 0; end <= given_string.length(); end++)
{
if(end == given_string.length() || str[end] == ' ')
{
reverseString(str, start, end-1);
start = end + 1;
}
}
return new String(str);
}
// In-place reverse string method
public static void reverseString(char[] str, int start, int end)
{
while(start < end)
{
char temp = str[start];
str[start++] = str[end];
str[end--] = temp;
}
}
Speichern Sie jedes Word als Zeichenfolge in einem Array und drucken Sie dann vom Ende aus
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]);
}
}
}
Wörter in umgekehrter Reihenfolge einer bestimmten Anweisung mit C # drucken:
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(' ');
}
}
}
Dieses Schnellprogramm funktioniert jedoch nicht. Die Eckfälle werden jedoch nicht überprüft.
#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");
}
Eine Möglichkeit, dies zu tun, besteht darin, jedes Wort unserer Eingabezeichenfolge zu analysieren und in einen LIFO -Stapel zu schieben.
Nachdem der gesamte String verarbeitet wurde, ziehen wir jedes Word einzeln aus dem Stapel heraus und hängen es an ein StringBuffer-Klassenobjekt an, das schließlich den umgekehrten Eingabe-String enthält.
Dies ist eine mögliche Lösung in Java, die StringTokenizer und die Stack-Klasse verwendet. Wir müssen Java.util.Stack importieren.
public String revString(String input)
{
StringTokenizer words=new StringTokenizer(input); //Split the string into words
Stack<String> stack= new Stack<String>();
while(words.hasMoreTokens())
{
stack.Push(words.nextElement().toString()); // Push each Word of the string onto stack.
}
StringBuilder revString=new StringBuilder();
while(!stack.empty())
{
revString.append(stack.pop()+" ");// pop the top item and append it to revString
}
return revString.toString();
}
Mit sscanf geht das einfacher:
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;
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ReverseString
{
class Program
{
static void Main(string[] args)
{
string StringReverse = "";
int StringLength;
do
{
Console.WriteLine("Enter the String : ");
string InputString = Console.ReadLine();
Console.WriteLine("Enter the length : ");
int InputLength = Convert.ToInt32(Console.ReadLine());
int NewLength = InputLength;
InputLength = InputLength - 1;
int LengthString = InputString.Length;
int l = LengthString - NewLength;
StringReverse = "";
while (InputLength >= 0)
{
StringReverse = StringReverse + InputString[InputLength];
InputLength--;
}
String substr = InputString.Substring(NewLength, l);
Console.WriteLine("Reverse String Is {0}", StringReverse + substr);
Console.WriteLine("\tDo you Want to CONTINUE?\n\t1.YES\n\t2.NO");
StringLength = Convert.ToInt32(Console.ReadLine());
}
while (StringLength == 1);
}
}
}
Hier ist der Algorithmus:
- Explodieren Sie die Zeichenfolge mit Leerzeichen und bilden Sie ein Array aus Wörtern.
- Kehren Sie das Array um.
- Implodieren Sie das Array nach Leerzeichen.
In c könnten Sie dies tun, O(N) und nur O(1) - Datenstrukturen (d. H. Ein Zeichen) verwenden.
#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;
}
public class reversewords {
public static void main(String args[])
{
String s="my name is nimit goyal";
char a[]=s.toCharArray();
int x=s.length();
int count=0;
for(int i=s.length()-1 ;i>-1;i--)
{
if(a[i]==' ' ||i==0)
{ //System.out.print("hello");
if(i==0)
{System.out.print(" ");}
for(int k=i;k<x;k++)
{
System.out.print(a[k]);
count++;
}
x=i;
}count++;
}
System.out.println("");
System.out.println("total run =="+count);
}
}
ausgabe: goyal nimit ist mein Name
gesamtlauf == 46
Der einfachste Weg dies zu tun ..
string inputStr = "My name is X Y Z";
string outputStr = string.Empty;
List<string> templist1 = new List<string>();
templist1 = inputStr.Split(' ').ToList();
for (int i = templist1.Count- 1 ; i >= 0; i--)
{
if (outputStr != string.Empty)
{
outputStr = outputStr + " " + templist1[i];
}
else
{
outputStr = templist1[i];
}
}
Console.WriteLine("Reverse of a String is", outputStr);
Output:
Z Y X is name My
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);
}
So machen Sie es in Excel als UDF und in VBA:
Public Function ReverseMe(textToReverse As String, _
Optional delim As String = " ") As String
Dim test As String
Dim arr As Variant
Dim arr2 As Variant
Dim arrPart As Variant
Dim cnt As Long
arr = Split(textToReverse, ".")
ReDim arr2(UBound(arr))
For Each arrPart In arr
arr2(cnt) = StrReverse(arrPart)
cnt = cnt + 1
Next arrPart
ReverseMe = StrReverse(Join(arr2, "."))
End Function
Public Sub TestMe()
Debug.Print ReverseMe("veso.dosev.diri.rid", ".")
Debug.Print ReverseMe("VBA is the best language")
End Sub
Ich weiß, dass es mehrere richtige Antworten gibt. Hier ist der in C, den ich mir ausgedacht habe ... Dies ist eine Implementierung der ausgenommenen Antwort. Die Zeitkomplexität ist O(n) und es wird kein zusätzlicher String verwendet.
#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;
}
Eigentlich die erste Antwort:
words = aString.split(" ");
for (i = 0; i < words.length; i++) {
words[i] = words[words.length-i];
}
funktioniert nicht, weil es in der zweiten Hälfte der Schleife die Arbeit rückgängig macht, die es in der ersten Hälfte geleistet hat. Ich würde also <words.length/2 funktionieren, aber ein klareres Beispiel ist folgendes:
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; //i.e. swap the elements
i++;
j--;
}
Hinweis: Ich bin mit der Syntax PHP nicht vertraut und habe die Inkrementer- und Decrementer-Syntax erraten, da sie anscheinend ähnlich zu Perl ist.
string = "hello world";
strrev = ""
list = [];
def splitstring(string):
j = 0;
for i in range(0,len(string)):
if(string[i] == " "):
list.append(string[j:i]);
j = i+1;
Elif (i+1 == len(string)):
list.append(string[j:i+1]);
splitstring(string);
for i in list:
for j in range(len(i)-1,-1,-1):
strrev += i[j];
if (i != list[-1]):
strrev+= " ";
print(list);
print(":%s:" %(strrev));
In Java
package Test;
public class test2 {
public static void main(String[] args){
String str = "my name is fawad X Y Z";
String strf = "";
String strfinal="";
if (str != ""){
for (int i=0 ; i<=str.length()-1; i++){
strf += str.charAt(str.length() - (i+1));
}
System.out.println(strf);
}
else System.out.println("String is Null");
if (strf != ""){
String[] temp = strf.split(" ");
String temp1 = "";
System.out.println(temp.length);
for (int j=0; j<=temp.length-1; j++){
temp1 = temp[j];
if(temp1.length()>1){
for (int k=0; k<=temp1.length()-1; k++){
strfinal += temp1.charAt(temp1.length()-(1+k));
}
strfinal += " ";
}
else strfinal += temp1 + " ";
}
System.out.println(strfinal);
}
else System.out.println("String Final is Null");
}
}
Ausgabe:
Z Y X dawaf si eman ym
Z Y X fawad is name my
public static void main(String args[]) {
String str = "My name is X Y Z"; // out put "Z Y X is name My"
// split
String[] arr = str.split(" ");
// reverse Word
String reverse = "";
for (int i = arr.length - 1; i >= 0; i--) {
if(i!=0){
reverse += arr[i]+" ";
}else{
reverse += arr[i];
}
}
System.out.println(reverse);
}
Diese Frage wird im Paytm-Interview für Java-Position gestellt. Ich finde die folgende Lösung.
class ReverseStringWord{
public static void main(String[] args) {
String s="My name is X Y Z";
StringBuilder result=new StringBuilder();
StringBuilder str=new StringBuilder();
for(int i=0;i<s.length();i++){
if(s.charAt(i)==' '){
result.insert(0,str+" ");
str.setLength(0);
}
else{
str.append(s.charAt(i));
if(i==s.length()-1){
result.insert(0,str+" ");
}
}
}
System.out.println(result);
}}
In Java mit einem zusätzlichen String (mit 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();
}
In Java vor Ort:
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];
}
}
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]);
}
}
}
Bessere Version
Überprüfen Sie mein Blog 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;
}
Hier ist eine C-Implementierung, die das Word-Inlace umkehrt und O(n)-Komplexität aufweist.
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;
}
So lösen Sie es in TCL, unabhängig davon, wie viele Leerzeichen oder Tabulatoren oder neue Zeilen (\ n) in Ihrer Zeichenfolge vorhanden sind. Dies ist eine reale Lösung und die menschliche Denkweise. Es betrachtet nicht ein und nur ein Leerzeichen ist ein Zeichen eines neuen Wortes.
Und ich denke, in C/C++ und Java kann man es genauso übersetzen.
Ich habe vor diesem Beitrag zwei Tage daran gearbeitet, weil ich nicht akzeptierte, dass es Funktionen gibt, die von der Bibliothek der Sprache bereitgestellt werden, die auch für uns gemacht wurden, und wir sie nicht verwenden.
<!-- language: lang-php -->
# 1- Reverse the orignial text
set reversed [ string reverse $all_original_text]
# 2- split the reversed string $reversed into a list of words then loop over them
set list_of_reversed_words [split $reversed ]
foreach reversed_words $list_of_reversed_words {
# 3- find the indices of the extremes of each reversed Word in the $reversed
set Word_start [ string first $reversed_words $reversed $Word_start]
set Word_end [ expr $Word_start -1 + [string length $letter] ]
# 4- reverse the current-in-the-loop reversed Word back to its normal state, e.g:
# if i have a Word "loohcs" then convert it by reversing it to "school"
set original_Word [string reverse [ string range $reversed $Word_start $Word_end] ]
# 5- replace the reversed Word (loohcs) with the correcte one (school)
set reversed [ string replace $reversed $Word_start $Word_end $original_Word]
# 6- set the start-of-search index to the index
# directly after the ending of the current Word
set Word_start [expr $Word_end +1]
# 7-continue to the next loop
}
#print the result
puts "finally: $reversed"
public class StringReverse {
public static void main(String[] args) {
StringReverse sr =new StringReverse();
String output=sr.reverse("reverse this string");
String substring="";
for(int i=0;i<=output.length();i++)
{
if(i==output.length()){
System.out.print(sr.reverse(substring));
substring="";
}else if(output.charAt(i)==' ' ){
System.out.print(sr.reverse(substring+" "));
substring="";
}
if(i<output.length())
{
substring+=output.charAt(i);}
}
}
public String reverse(String str){
char[] value=str.toCharArray();
int count=str.length();
int n = count - 1;
for (int j = (n-1) >> 1; j >= 0; --j) {
char temp = value[j];
value[j] = value[n - j];
value[n - j] = temp;
}
return new String(value);
}
}
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
void reverse(char *data, int len) {
int counter = 0;
int end = len - 1;
char temp;
for (counter = 0; counter < len / 2; counter++, end--) {
temp = data[counter];
data[counter] = data[end];
data[end] = temp;
}
}
int main(void) {
char data[] = "This is a line and needs to be reverse by words!";
int c = 0;
int len = strlen(data);
int wl = 0;
int start = 0;
printf("\n data = %s", data);
reverse(data, len);
for (c = 0; c < len; c++) {
if (!wl) {
start = c;
}
if (data[c] != ' ') {
wl++;
} else {
reverse(data + start, wl);
wl = 0;
}
}
printf("\nnow data = %s", data);
return EXIT_SUCCESS;
}
Hier ist ein netter Tweak für diejenigen, die die Frage mochten ... was ist, wenn das Alphabet, aus dem die getauschten Wörter bestehen, kleiner als 16 Zeichen ist (16 einschließlich "Leerzeichen")? Es gibt viele Beispiele für solche Alphabete: die numerischen Zeichen [01234567890 .- +], die Genombuchstaben [GATC], das hawaiianische Alphabet [aeiouhklmnpv?], den Morsecode [-.], die Noten [ABCDEFG # m] usw. Dies ermöglicht das Kodieren der Zeichen als Halbbytes (4 Bit) und das Speichern von zwei kodierten Zeichen in einem 8-Bit-Zeichen.
Es ist immer noch nicht trivial, die Wörter in einer einzelnen Schleife zu tauschen, wobei sich ein Cursor von links nach rechts und der andere von rechts nach links bewegt. Es gibt vier Arten von Word-Kopieren: Kopieren Sie ein Word von links nach rechts, von rechts nach links und die beiden äquivalenten Kopien, bei denen Lese- und Schreibüberlappungen auftreten: Position X-> X + y und X-> Xy, wobei y kleiner als die Länge von X ist.
Die Optimierung von Nice ist, dass während der ersten Hälfte der Schleife Wörter von der rechten Seite in die linke kodiert werden (wobei die ursprünglichen linken Werte erhalten bleiben), aber in der zweiten Hälfte können die Wörter von links direkt nach rechts und dann nach links kopiert werden Zeichen werden mit ihren endgültigen Werten überschrieben ...
Hier ist der C-Code, der ein beliebiges Alphabet als Parameter verwendet:
#define WORDS_DELIMITER ' '
#define UNMAPPED 0xFF
#define BITS_IN_NIBBLE 4
#define BITS_IN_BYTE 8
#define CHARS_IN_NIBBLE (1 << BITS_IN_NIBBLE)
#define CHARS_IN_BYTE (1 << BITS_IN_BYTE)
typedef union flip_char_ {
unsigned char clear;
struct {
unsigned char org:4;
unsigned char new:4;
} encoded;
} flip_char_t;
typedef struct codec_ {
unsigned char nibble2ascii[CHARS_IN_NIBBLE];
unsigned char ascii2nibble[CHARS_IN_BYTE];
} codec_t;
static int
codec_init (const unsigned char *alphabet, codec_t *codec)
{
size_t len = strlen(alphabet), i;
if (len > CHARS_IN_NIBBLE) {
fprintf(stderr, "alphabet is too long!\n");
return -1;
}
if (strchr(alphabet, WORDS_DELIMITER) == NULL) {
fprintf(stderr, "missing space in the alphabet\n");
return -1;
}
strcpy(codec->nibble2ascii, alphabet);
memset(codec->ascii2nibble , UNMAPPED, CHARS_IN_BYTE);
for (i=0; i<len; i++) {
codec->ascii2nibble[ alphabet[i] ] = i;
}
return 0;
}
static inline int
is_legal_char (const codec_t *codec, const unsigned char ch)
{
return codec->ascii2nibble[ch] != UNMAPPED;
}
static inline unsigned char
encode_char (const codec_t *codec, unsigned char org, unsigned char new)
{
flip_char_t flip;
flip.encoded.org = codec->ascii2nibble[org];
flip.encoded.new = codec->ascii2nibble[new];
return flip.clear;
}
static inline unsigned char
decode_org (const codec_t *codec, unsigned char ch)
{
flip_char_t flip = { .clear = ch };
return codec->nibble2ascii[flip.encoded.org];
}
static inline unsigned char
decode_new (const codec_t *codec, unsigned char ch)
{
flip_char_t flip = { .clear = ch };
return codec->nibble2ascii[flip.encoded.new];
}
// static void inline
// encode_char (const char *alphabet, const char *
static int
flip_words (const unsigned char *alphabet, unsigned char *a, size_t len)
{
codec_t codec; /* mappings of the 16char-alphabet to a nibble */
int r=len-1; /* right/reader cursor: moves from right to left scanning for words */
int l=0; /* left/writer cursor: moves from left to right */
int i=0; /* Word iterator */
int start_Word=-1,end_Word=-1; /* Word boundaries */
unsigned char org_r=0; /* original value pointed by the right cursor */
int encode=0, rewrite=0; /* writing states */
if (codec_init(alphabet, &codec) < 0) return -1;
/* parse the buffer from its end backward */
while (r>=0) {
if (r>=l && !is_legal_char(&codec, a[r])) {
fprintf(stderr, "illegal char %c in string\n", a[r]);
return -1;
}
/* read the next charachter looking for Word boundaries */
org_r = (r<l) ? decode_org(&codec, a[r]) : a[r];
/* handle Word boundaries */
if (org_r == WORDS_DELIMITER) {
/* mark start of Word: next char after space after non-space */
if (end_Word>0 && start_Word<0) start_Word = r/*skip this space*/+1;
/* rewrite this space if necessary (2nd half) */
if (r<l) a[r] = decode_new(&codec,a[r]);
} else {
/* mark end of Word: 1st non-space char after spaces */
if (end_Word<0) end_Word = r;
/* left boundary is a Word boundary as well */
if (!r) start_Word = r;
}
/* Do we have a complete Word to process? */
if (start_Word<0 || end_Word<0) {
r--;
continue;
}
/* copy the Word into its new location */
for(i=start_Word; i<=end_Word; i++, l++) {
if (i>=l && !is_legal_char(&codec, a[l])) {
fprintf(stderr, "illegal char %c in string\n", a[l]);
return -1;
}
/* reading phase: value could be encoded or not according to writer's position */
org_r= (i<l) ? decode_org(&codec, a[i]) : a[i];
/* overlapping words in shift right: encode and rewrite */
encode=rewrite=(l>=start_Word && l<=end_Word && i<l);
/* 1st half - encode both org and new vals */
encode|=(start_Word-1>l);
/* 2nd half - decode and rewrite final values */
rewrite|=(i<l);
/* writing phase */
a[l]= encode ? encode_char(&codec, a[l], org_r) : org_r;
if (rewrite) {
a[i]=decode_new(&codec, a[i]);
}
}
/* done with this Word! */
start_Word=end_Word=-1;
/* write a space delimiter, unless we're at the end */
if (r) {
a[l] = l<r ? encode_char(&codec, a[l], WORDS_DELIMITER) : WORDS_DELIMITER;
l++;
}
r--;
}
a[l]=0;
return 0; /* All Done! */
}
Ich habe das Problem gelöst, ohne extra Speicherplatz zu verwenden, nur die ursprüngliche Zeichenfolge selbst. Aber ich konnte das Problem in O (n) nicht lösen. Das Mindeste, was ich bekommen könnte, ist O (n-Quadrat), das für den ungünstigsten Fall gilt Szenario.
So wie ich es umgesetzt habe -
- Den ganzen Satz umkehren, Zeichen für Zeichen.
- Später iteriere ich den ganzen Satz, aber dieses Mal stelle ich jedes Wort um.
Und deshalb habe ich die schlechteste Komplexität als O (n sqaure)
Bitte finden Sie den Code unten in Java. Ich hoffe, es hilft jemandem.
class MainClass {
public static void main(String args[]) {
String str = "reverse me! also lets check";
System.out.println("The initial string is --->> " + str);
for (int i = 0; i < str.length(); i++) {
//Keep iterating each letter from one end to another.
str = str.substring(1, str.length() - i)
+ str.substring(0, 1)
+ str.substring(str.length() - i, str.length());
}
System.out.println("The reversed string is ---->> " + str);
for (int i = 0, j = 0; i < str.length(); i++) {
if(str.charAt(i) == ' ' || i == (str.length() - 1)) {
//Just to know the start of each Word
int k = j;
//the below if condition is for considering the last Word.
if(i == (str.length() - 1)) i++;
while(j < i) {
j++;
str = str.substring(0, k)
//(i-j) is the length of each Word
+ str.substring(k + 1, (k + 1) + i - j)
+ str.substring(k, k + 1)
+ str.substring((k + 1) + i - j, i)
+ str.substring(i);
if(j == i) {
//Extra j++ for considering the empty white space
j++;
}
}
}
}
System.out.println("The reversed string but not the reversed words is ---->> " + str);
}
}
Verwendungszweck
char str[50] = {0};
strcpy(str, (char*)"My name is Khan");
reverseWords(str);
Methode
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;
}
}
c # Lösung, um Wörter in einem Satz umzukehren
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);
}
}
ausgabe: Peaople das Herz der Schönheit liegt Drücken Sie eine beliebige Taste, um fortzufahren. . .
Wie wäre es mit ...
var words = "My name is X Y Z";
var wr = String.Join( " ", words.Split(' ').Reverse().ToArray() );
Ich denke, das ist kein Inline-Tho.
Mit Java:
String newString = "";
String a = "My name is X Y Z";
int n = a.length();
int k = n-1;
int j=0;
for (int i=n-1; i>=0; i--)
{
if (a.charAt(i) == ' ' || i==0)
{
j= (i!=0)?i+1:i;
while(j<=k)
{
newString = newString + a.charAt(j);
j=j+1;
}
newString = newString + " ";
k=i-1;
}
}
System.out.println(newString);
Die Komplexität ist O(n) [Durchqueren des gesamten Arrays] + O(n) [Durchqueren jedes Wortes erneut] = O (n)