Created
June 20, 2017 23:28
-
-
Save jianminchen/c6259abd3c5891d4669daeac9f75d646 to your computer and use it in GitHub Desktop.
reverse words in a string - April practice
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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