Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/c6259abd3c5891d4669daeac9f75d646 to your computer and use it in GitHub Desktop.
Save jianminchen/c6259abd3c5891d4669daeac9f75d646 to your computer and use it in GitHub Desktop.
reverse words in a string - April practice
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace reverseWordsInMay
{
/// <summary>
/// April, 2017
/// Should use in place swap, do not use extra space
/// </summary>
class Program
{
static void Main(string[] args)
{
var result = ReverseOrderOfWordsLinearScan(new char[]{'a',' ','b', ' ','c'}, ' ');
}
public static char[] ReverseOrderOfWordsLinearScan(char[] words, char delimiter)
{
string reversedWord = string.Empty;
if(words == null || words.Length == 0)
{
return reversedWord.ToCharArray();
}
int length = words.Length;
reverseString(words, 0, length - 1);
// space " aaa", skip first few spaces
int start = 0;
int end = 0;
for(int i = 0; i < length; i++)
{
char current = words[i];
if(current != delimiter)
{
end = i;
}
else if(current == delimiter)
{
if(end > start)
{
reverseString(words, start, end);
start = i + 1;
end = i + 1;
}
else
{
start = i+1;
end = i+1;
}
}
}
return words;
}
// O(n)
// char[] output- char[]
// char[] -> string-> char[]
// char [ a, b, c] -> i=0, j=2 swap() -> k=char[0]=a, char[
// return char[]
// in place - swap both end <
private static void reverseString(char[] words, int start, int end)
{
while (start < end)
{
var tmp = words[start];
words[start] = words[end];
words[end] = tmp;
start++;
end--;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment