Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Given s = "the sky is blue",
return "blue is sky the".
Could you do it in-place without allocating extra space?
Allocating Extra space for output
var input = "ayman ali";
input = " " + input;
var arr = input.ToCharArray();
var output = string.Empty;
var b = 0;
var e = arr.Length;
for (int p = arr.Length - 1; p >= 0; p--)
{
if (arr[p] == ' ' )// little off beginning of word
{
b = p + 1;
output += input.Substring(b, e - b) + " ";
e = p ;
}
}
Console.WriteLine(output.TrimEnd(' '));
Console.ReadLine();
Without allocating extra space
//Reverse words in string
var input = "ayman ali";
input = input + " ";
var arr = input.ToCharArray();
//Loop - Pointer (p) is index - Length is length of array
//If space found - e = p - 1, begin (b) saved from before
//Reverse string in place
//Loop half length of string
//i to m (Mirror) m = e-i
//Reverse whole string
var b = 0;
var e = 0;
for (int p = 0; p < arr.Length ; p++)
{
if (arr[p] == ' ')
{
e = p - 1;
for (int i = b; i < (b+ (e-b) /2); i++)
{
var temp = arr[i];
var m = e - (i - b);
arr[i] = arr[m];
arr[m] = temp;
}
b = p + 1;
}
}
//arr need to be revsrsed
e = arr.Length-1;
for (int p = 0; p < e/2; p++)
{
var temp = arr[p];
var m = e - p - 1;
arr[p] = arr[m];
arr[m] = temp;
}
Console.WriteLine(string.Join(string.Empty, arr.Take(e)));
Console.ReadLine();
No comments:
Post a Comment