Facebook Interview Question
Software Engineer / DevelopersTeam: iOS
Country: United States
Interview Type: In-Person
If I am wrong, pls correct me. The time complexity is O(n);
I use a stack to reverse the whole sequence of the string then split them by space.
input: @"the boy ran"
output: @"eht yob nar"
import java.util.Scanner;
import java.util.Stack;
public class test {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String thestring = input.nextLine();
input.close();
thestring = thestring.substring(2, thestring.length()-1);
Stack<Character> st = new Stack<Character>();
for(int i=0; i<thestring.length(); i++)
{
st.push(thestring.charAt(i));
}
thestring = "";
while(!st.empty())
{
thestring = thestring + st.peek();
st.pop();
}
String[] stringArray = thestring.split(" ");
System.out.print("@\"");
for(int i=stringArray.length-1; i>=0; i--)
{
if(i==0)
System.out.print(stringArray[i]);
else
System.out.print(stringArray[i]+" ");
}
System.out.print("\"");
}
}
Your space complexity is pretty high - You are using stack and then a String[] etc. Can we do better?
We can do it by using an simple character array. I am using an character array (string, we can also use StringBuffer to avoid objects overhead) ...
public static String reverse(String input){
if(input == null){
return null;
}
String output = "";
String tmp = String.valueOf(input.charAt(0));
for(int i = 1; i < input.length(); i++){
if(input.charAt(i) ==' '){
output = output + tmp + ' ';
tmp = "";
}else{
tmp = input.charAt(i) + tmp;
}
}
//Append last word
output = output + ' ' + tmp;
return output;
}
Space O(N), Time O(N)
It can be done inplace. In this case you have to traverse each word twice.
1) Find a word, reverse it.
2) skip all the spaces or keep it as those are.
void reverseWords(String s) {
int start, end;
start = end = 0;
int len = s.length();
while (start < length) {
while ((start < length) && (s.charAt(start) == ' ')) start++;
end = start;
if (end < length) {
while( end < lenght -1 && s.charAt(end + 1) != ' ') {
end++;
}
}
if (start < end) reverseString(s, start, end);
start = end+1;
}
}
void reverseWord(String s, int start, int end) {
while(start < end) {
char c = s.charAt(end);
s.set(end, s.charAt(start));
s.set(start, c);
start++;
end--;
}
}
Solution in Objective-C leveraging categories. Worst case complexity is O(n + n/2) = O(n).
Tests first:
//
// CSPWordInverterTests.m
//
#import <XCTest/XCTest.h>
#import "NSString+WordInverter.h"
@interface CSPWordInverterTests : XCTestCase
@end
@implementation CSPWordInverterTests
- (void)setUp
{
[super setUp];
// Put setup code here. This method is called before the invocation of each test method in the class.
}
- (void)tearDown
{
// Put teardown code here. This method is called after the invocation of each test method in the class.
[super tearDown];
}
- (void)testSimpleCase
{
XCTAssertEqualObjects(@"eht yob nar", [@"the boy ran" invertWords]);
}
- (void)testNullOrEmptyData
{
XCTAssertNil([(NSString*)nil invertWords]);
XCTAssertEqualObjects(@"", [@"" invertWords]);
XCTAssertEqualObjects(@" ", [@" " invertWords]);
}
- (void)testStringWithNoWords
{
XCTAssertEqualObjects(@" %^& *$@", [@" %^& *$@" invertWords]);
XCTAssertEqualObjects(@"$", [@"$" invertWords]);
}
- (void)testStringsWithOneWord
{
XCTAssertEqualObjects(@"one", [@"eno" invertWords]);
}
- (void)testPalindromes
{
XCTAssertEqualObjects(@"ema a ame", [@"ame a ema" invertWords]);
XCTAssertEqualObjects(@"dabalearrozalazorraelabad",
[@"dabalearrozalazorraelabad" invertWords]);
}
- (void)testAMoreComplexSentence
{
XCTAssertEqualObjects(@"ehT ecnednepednI fo aciremA saw deralced " \
@"a ht4 fo yluJ fo 6771.",
[@"The Independence of America was declared " \
@"a 4th of July of 1776." invertWords]);
}
@end
Category header:
//
// NSString+WordInverter.h
//
#import <Foundation/Foundation.h>
/**
* Category over NSString that features a method to reverse the order of
* characters in all words of a string.
*/
@interface NSString (WordInverter)
/**
* Reverses the order of the characters in all words of the string.
*/
- (NSString*)invertWords;
@end
Implementation:
//
// NSString+WordInverter.mm
//
#import "NSString+WordInverter.h"
#include <ctype.h>
void invertWord(unichar* buffer, NSUInteger begin, NSUInteger end)
{
// Defensive coding: attention to the case end is 0 (beginning of sentence)
if (end) {
for (--end; begin < end; ++begin, --end) {
// swapping via XOR
buffer[begin] = (buffer[begin] ^ buffer[end]);
buffer[end] = (buffer[begin] ^ buffer[end]);
buffer[begin] = (buffer[begin] ^ buffer[end]);
}
}
}
@implementation NSString (WordInverter)
- (NSString*)invertWords
{
NSString* result = nil;
NSUInteger length = [self length];
if (length) {
unichar* buffer = new unichar[length];
@try {
NSUInteger foreRunner = 0, backRunner = 0;
BOOL traversingWord = YES;
while (foreRunner < length) {
buffer[foreRunner] = [self characterAtIndex:foreRunner];
if (traversingWord) {
if (!(traversingWord = isalnum(buffer[foreRunner]))) {
// we are past-the-word-end, we must invert the word
invertWord(buffer, backRunner, foreRunner);
}
} else {
if ((traversingWord = isalnum(buffer[foreRunner]))) {
// end of non-alpha segment: beginning of word
backRunner = foreRunner;
}
}
++foreRunner;
}
// border condition: string may end while traversing a word
if (traversingWord) invertWord(buffer, backRunner, foreRunner);
result = [NSString stringWithCharacters:buffer length:length];
}
@finally {
delete[] buffer;
}
} else {
result = [NSString string];
}
return result;
}
@end
<?php
class Stack {
private $top = 0;
private $data = [];
public function push($char) {
$this->data[$this->top] = $char;
$this->top++;
}
public function popAll() {
$result = '';
for ($i = $this->top; $i > 0; $i--) {
$result .= $this->data[$i - 1];
}
$this->top = 0;
return $result;
}
}
function invertWord($content) {
$stack = new Stack();
for ($i = 0; $i < strlen($content); $i++) {
if ($content[$i] != ' ') {
$stack->push($content[$i]);
continue;
}
$output = $stack->popAll();
echo "$output ";
}
$output = $stack->popAll();
echo "$output\n";
}
invertWord('the boy ran');
public void reverseWordsOfStringInPlace(String word){
StringBuilder sb = new StringBuilder();
StringBuilder rsb = new StringBuilder();
for (int i = word.length()-1; i >=0 ; i--) {
if(word.charAt(i)!=' '){
sb.append(word.charAt(i));
}else{
rsb.append(sb + " ");
sb = new StringBuilder();
}
}
rsb.append(sb + " ");
System.out.println(rsb);
}
def reverse_each_word_of(sentence):
word_list = sentence.split()
for i in range(len(word_list)):
word_list[i] = word_list[i][::-1]
return ' '.join(word_list)
O(n) solution
string input = @"The boy run";
StringBuilder builder = new StringBuilder();
int i =0;
string temp;
bool isFirstInsert = true;
while(i< input.length)
{
if(input[i] != ' ')
{
temp= input[i].ToString() + temp;
}
else
{
if(! isFirstInsert)
{
builder.append(" ");
}
builder.append(temp);
temp =string.Empty;
}
i++;
}
string output = builder.ToString();
Written with a hard-coded string, but can easily be modified to use arguments passed to the function
void reverse_words_in_place()
{
char src[] = "the boy ran";
cout << "Reversing words in place" << endl;
cout << src << endl;
string res("");
char *tok = strtok(src, " ");
while(tok != NULL)
{
string s(tok);
res += string(s.rbegin(), s.rend());
tok = strtok(NULL," ");
if(tok != NULL)
{
res += " ";
}
}
cout << res << endl;
}
Complexity is O(n), and linear on the average length of a word. So if N, with N being the number of words, is larger then the complexity will be O(N), while if m, the average length of words, is larger than N then the complexity will be O(m)
Looking at this, I can see where it might be N-squared due to the use of the string's += operator, which in C++ has an unspecified complexity but can be up to linear. I may rewrite this to use separate pointers that then swap through each word instead, but I like this solution for its readability.
static Stack<String> stack;
public static String reverseString(String stringToReverse)
{
StringBuilder builder = new StringBuilder();
stack = new Stack<String>();
char[] charArray = stringToReverse.toCharArray();
for(char character : charArray)
{
stack.add(String.valueOf(character));
}
while(stack.size() >0)
{
builder.append(stack.pop());
}
String[] individualString = StringUtils.split(builder.toString());
StringBuilder returnString = new StringBuilder();
for(int i=individualString.length-1; i>=0 ; i--)
{
returnString.append(individualString[i]);
returnString.append(" ");
}
return returnString.toString();
}
void reverse(char sub_str[], int begin, int end) {
char temp;
while (begin < end) {
temp = sub_str[begin];
sub_str[begin] = sub_str[end];
sub_str[end] = temp;
begin++;
end--;
}
}
void reverseWords(char str[], int N) {
int begin = 0, end = 0;
while(end < N) {
while (end != " " && end != '\0') {
end++;
}
reverse(str, begin, end); // This simply reverses a string
end++;
begin = end;
}
}
---
O(N) + O(N/2)
class Program
{
static void Main(string[] args)
{
string strtoFlip = @"the boy ran";
var arr = strtoFlip.ToCharArray();
swapWords(arr);
Console.Write(new string(arr));
Console.ReadKey();
}
public static void swapWords(char[] arr, int start = 0)
{
// return if done
if (start >= arr.Length) return;
//find end of word
int pos = start;
while (pos < arr.Length && arr[pos] != ' ') pos++;
//reverse word
revWord(arr,start,pos-1);
// start over, but from position after the word
swapWords(arr,pos+1);
}
public static void revWord(char[] arr, int s, int e)
{
if (arr==null||
s<0||e<0||
s>arr.Length||e>arr.Length) return;
while (s < e)
swapchar(arr, s++, e--);
}
public static void swapchar(char[] arr, int p1, int p2)
{
char temp;
temp = arr[p1];
arr[p1] = arr[p2];
arr[p2] = temp;
}
}
The naive solution would be to split the string, then reverse each substring. Many responses claim this is `O(n)`, but this is incorrect. Splitting the string is `O(n)`. Reversing a string is `O(n)`. If a split produces `m` substrings, each of them must be reversed, which is `O(mn)`, or `O(n^2)`.
A more efficient solution is as follows:
1. Initialize `reversed`, an empty, mutable string, and `reversedIndex`, the index at which we will insert characters into the reversed string.
2. Iterate over the original string in reverse order.
3. For each character in the original string, check whether it is whitespace.
3a. If it is, put it at the beginning of `reversed`, and reset `reversedIndex` to 0.
3b. If it is not, insert it into `reversed` at the `reversedIndex`. Then increment `reversedIndex`.
Objective-C code follows:
NSString *reversedWords(NSString *string) {
NSUInteger reversedIndex = 0;
NSMutableString *reversed = [NSMutableString string];
for (NSInteger i = [string length] - 1; i >= 0; --i) {
NSString *character = [string substringWithRange:NSMakeRange(i, 1)];
if ([character isEqualToString:@" "]) {
reversed = [NSMutableString stringWithFormat:@"%@%@", character, reversed];
reversedIndex = 0;
} else {
[reversed insertString:character atIndex:reversedIndex++];
}
}
return [reversed copy];
}
And here is the test:
- (void)testReversedWords {
NSString *reversed = cup_reversedWords(@"the boy ran");
XCTAssertEqualObjects(reversed, @"eht yob nar", @"");
reversed = cup_reversedWords(@"");
XCTAssertEqualObjects(reversed, @"", @"");
reversed = cup_reversedWords(@" ");
XCTAssertEqualObjects(reversed, @" ", @"");
reversed = cup_reversedWords(@"oneword");
XCTAssertEqualObjects(reversed, @"droweno", @"");
reversed = cup_reversedWords(@"oneword ");
XCTAssertEqualObjects(reversed, @"droweno ", @"");
}
You can improve the readability/maintainability of the code by replacing the call to `-isEqualToString:` with a category method. Also, you could add a method to `NSMutableString` that allows you to prepend a string to `reversed`, instead of using `+stringWithFormat:` like I did.
The split solution is indeed O(n), with n be the total number of characters in the input string. Even though we have to do reverse word multiple times, each word reverse only scan it's own number of characters, which all adds up to n. The problem with split solution is extra storage, not time.
public static void main(String args) {
String str = "why so serious";
String[] arr = str.split(" ");
StringBuffer stringBuffer = new StringBuffer();
for(String st : arr){
stringBuffer.append(reverseString(st)+ " ");
}
System.out.println(stringBuffer.toString().trim());
}
private static StringBuffer reverseString(String str) {
StringBuffer buffer = new StringBuffer(str);
return buffer.reverse();
}
function foo(a){
var b=a.split(" ");
var n=b.length;
while(n>0){
var reveredWord=reverseWord(b[b.length-n]);
b[b.length-n]=reveredWord;
n--;
}
a="";
for(var i=0;i<b.length;i++){
if(i!= n-1){
a+=b[i]+" ";
}else{
a+=b[i];
}
}
console.log(a);
}
function reverseWord(word){
console.log(word);
var n=word.length;
console.log(n);
var temp="";
while(n>=0){
temp=temp+word.charAt(n);
n--;
}
console.log(temp);
return temp;
}
foo("Vinay is a good boy");
public class Reverse {
private static String ReverseWord(String word)
{
int length = word.length();
int start = 0;
int end = length - 1;
char[] charArr = word.toCharArray();
while(start < end)
{
char temp = word.charAt(start);
charArr[start]= word.charAt(end);
charArr[end] = temp;
start++;
end--;
}
return new String(charArr);
}
private static String ReverseSentenceInPlace(String sentence)
{
String[] words = sentence.trim().split(" ");
int index = 0;
for(String word : words)
{
words[index] = ReverseWord(word);
index++;
}
return Arrays.toString(words);
}
public static void main(String[] args)
{
System.out.println(ReverseSentenceInPlace("the boy ran"));
}
}
Maybe I am seeing this wrong, people writing tons of code for such a simple program. Well dont blame me because it is from the view point of a student who is learning java.
import java.util.Scanner;
public class DoubleReverse
{
Scanner sc = new Scanner(System.in);
public String reverseString(String to_rev)
{
int length = to_rev.length();
String rev = "";
for(int i = 0; i<length; i++)
{
rev = to_rev.charAt(i) + rev;
}
return rev;
}
public void print()
{
System.out.println("Enter a string");
String input = sc.nextLine() + " ";
String sub;
int length = input.length();
int fi = 0, li;
for(int i = 0; i<length; i++)
{
if(input.charAt(i) == ' ')
{
li = i;
sub = input.substring(fi, li);
System.out.print(reverseString(sub) + " ");
fi = i + 1;
}
}
System.out.println("");
}
public static void main(String[]args)
{
DoubleReverse obj = new DoubleReverse();
obj.print();
}
}
+ (NSString *)reverseString:(NSString *)string {
NSMutableString *output = [NSMutableString string];
for (long i = string.length -1 ; i >= 0 ; i--) {
[output appendFormat:@"%c", [string characterAtIndex:i]];
}
return output;
}
+ (NSString *)reverseSentence:(NSString *)string {
NSArray *wordsArray = [string componentsSeparatedByString:@" "];
NSMutableArray *modArray = [NSMutableArray array];
for (NSString *word in wordsArray) {
[modArray addObject:[self reverseString:word]];
}
NSMutableString *output = [NSMutableString string];
for (NSString *word in modArray) {
[output appendFormat:@"%@ ", word];
}
return output;
}
public class TestProgram {
static final String INPUT_STRING = "the boy ran";
static final String SPACE = " ";
public static void main(String[] args) {
String words[] = INPUT_STRING.split(SPACE);
for (int i = 0; i < words.length; i++) {
System.out.print(new StringBuilder(words[i]).reverse() + SPACE);
}
}
}
O(n) solution with the use of Stack and no extra loops
public static void reverseWords(String str){
char[] a = str.toCharArray();
int start = 0;
int end = 0;
char prevChar = ' ';
for(int i = 0; i < a.length; i++){
if(i == a.length -1){
reverse(a, start, end);
}
if(prevChar == ' ' && a[i] == ' '){
start++;
end++;
continue;
}
if(a[i] == ' '){
reverse(a, start, end-1);
end++;
start = end;
}
else
end++;
prevChar = a[i];
}
System.out.println("\nReversed: " + new String(a));
}
public static void reverse(char[] a, int start, int end){
Stack<Character> s = new Stack<Character>();
for(int i = start; i <= end; i++){
s.push(a[i]);
}
for(int i = start; i <= end; i++){
a[i] = s.pop();
}
}
O(n + klogm) solution with the use of Stack, where k is number of words and m is the average size of each word.
public static void reverseWords(String str){
char[] a = str.toCharArray();
int start = 0;
int end = 0;
char prevChar = ' ';
for(int i = 0; i < a.length; i++){
if(i == a.length -1){
reverse(a, start, end);
}
if(prevChar == ' ' && a[i] == ' '){
start++;
end++;
continue;
}
if(a[i] == ' '){
reverse(a, start, end-1);
end++;
start = end;
}
else
end++;
prevChar = a[i];
}
System.out.println("\nReversed: " + new String(a));
}
public static void reverse(char[] a, int start, int end){
Stack<Character> s = new Stack<Character>();
for(int i = start; i <= end; i++){
s.push(a[i]);
}
for(int i = start; i <= end; i++){
a[i] = s.pop();
}
}
# Reverses each word in a string but keep their sequence same
def reverse_words(string):
return ' '.join(w[::-1] for w in string.split(' '))
def main():
string = raw_input ("Please enter a string> ")
output_string = reverse_words(string)
print "The output string is: %s" % (output_string)
if __name__ == "__main__":
main()
Ruby (not a developer language, I know, but it's what I need).
# As we traverse the string, push each non-blank character to an
# array. When we hit a blank, pop the array contents to the output
# string followed by a blank.
def reverse_words(input)
stack = []
outary = []
stringary = input.split('')
for character in stringary do
if character == ' '
# Pop the stack
while stack.length > 0 do
outary.push(stack.pop)
end
outary.push(' ')
else
# Push to the stack
stack.push(character)
end
end
# Final pops
while stack.length > 0 do
outary.push(stack.pop)
end
return outary.join('')
end
O(N)
import java.util.*;
public class Stringtoken {
int i;
public static void main(String[] args) {
// TODO Auto-generated method stub
String kalu = new String ();
String argentina;
System.out.println("enter your text here\n");
Scanner s = new Scanner(System.in);
String kutiya = s.nextLine();
StringTokenizer st = new StringTokenizer(kutiya," ");
while(st.hasMoreTokens())
{
argentina = st.nextToken();
StringBuffer sb = new StringBuffer(argentina);
sb.reverse();
kalu = kalu + sb + " ";
}
System.out.println(kalu);
}
}
using the automatic NSString enumeration reverses the string itself..
this would be the function
NSString * swapString(NSString *inputString) {
NSMutableArray *characters = [NSMutableArray array];
[inputString enumerateSubstringsInRange:NSMakeRange(0, inputString.length)
options:NSStringEnumerationByComposedCharacterSequences | NSStringEnumerationReverse
usingBlock:^(NSString *substring,
NSRange substringRange,
NSRange enclosingRange,
BOOL *stop) {
[characters addObject:substring];
}];
return [characters componentsJoinedByString:@""];
}
// Hello World --> olleH dlroW
void lib_reverseWords(char *pszStr)
{
char *pszStart = pszStr, *pszEnd = pszStr;
int nCharCount = 0;
if(!pszStr || !*pszStr)
return;
// ab ki baar --> ba ik raab
while(*pszStr != '\0')
{
if(*pszStr == ' ')
{
if(nCharCount >= 2)
{
pszEnd = pszStr - 1;
while(pszStart < pszEnd)
{
char chTemp = *pszStart;
*pszStart = *pszEnd;
*pszEnd = chTemp;
pszStart++;
pszEnd--;
}
}
nCharCount = 0;
}
else
{
if(nCharCount == 0)
pszStart = pszStr;
nCharCount++;
}
pszStr++;
}
if(nCharCount >= 2)
{
pszEnd = pszStr - 1;
while(pszStart < pszEnd)
{
char chTemp = *pszStart;
*pszStart = *pszEnd;
*pszEnd = chTemp;
pszStart++;
pszEnd--;
}
}
}
public static void reverseString(String s){
char[] output = new char[s.length()];
for(int i=s.length()-1;i>=0;i--)
output[s.length()-1-i]=s.charAt(i);
String[] o = String.valueOf(output).split(" ");
for(int i=0; i<o.length; i++){
if(i>0 && i<o.length)
System.out.print(" ");
System.out.print(o[o.length-1-i]);
}
System.out.println();
}
O(n)
# reverse just words in a string
def reverse_whole(mystr)
i=0
while(i<mystr.size && mystr[i] == ' ')
i+=1
end
while(i<mystr.size)
j=i
while(j<mystr.size && mystr[j]!=' ')
j+=1
end
reverse(mystr,i,j-1)
i=j+1
end
puts mystr
end
#reverse a word
def reverse(mystr,i,j)
while(i<j)
tmp = mystr[i]
mystr[i] = mystr[j]
mystr[j] = tmp
i+=1
j-=1
end
end
# Run Result
reverse_whole(" the boy ran hello ")
eht yob nar olleh
# reverse words in a string
def reverse_whole(mystr)
i=0
while(i<mystr.size && mystr[i] == ' ')
i+=1
end
while(i<mystr.size)
j=i
while(j<mystr.size && mystr[j]!=' ')
j+=1
end
reverse(mystr,i,j-1)
i=j+1
end
puts mystr
end
def reverse(mystr,i,j)
while(i<j)
tmp = mystr[i]
mystr[i] = mystr[j]
mystr[j] = tmp
i+=1
j-=1
end
end
Time O(n), space O(1), if string were mutable in Java.
Keep two indexes, one for word begin and the other for word end. Scan input character by character, when a space character is found, reverse the word between begin and end. Update the indexes and repeat the reverse work, until the end of input.
public static String reverseWord(String str) {
//Not have to convert string to char array.
//In Java string is immutable, so one needs use extra space to do string operation.
//The most economic way is operate chars.
//If string were mutable, one can reverse string in place using string functions such as str.getCharAt(index) and str.setCharAt(index, value) to swap.
char[] chars = str.toCharArray();
int begin=0, end=0;
while (end<chars.length) {
end++;
if (end==chars.length||chars[end]==' ') {
reverse(chars, begin, end-1);
begin = end+1;
}
}
return new String(chars);
}
private static char[] reverse(char[] chars, int begin, int end) {
char temp;
while (begin<end) {
temp = chars[begin];
chars[begin] = chars[end];
chars[end] = temp;
begin++;
end--;
}
return chars;
}
public static void main(String[] args){
String s="the boy ran";
solve(s);
}
static void solve(String _s){
String[] s=_s.split(" ");
StringBuilder r=new StringBuilder();
for(int i=0;i<s.length;i++){
for(int j=s[i].length()-1;j>=0;j--){
r.append(s[i].charAt(j));
}
r.append(" ");
}
System.out.println(r);
public static void reverseWords(String s){
StringBuilder result = new StringBuilder();
StringTokenizer st = new StringTokenizer(s, " ");
while (st.hasMoreTokens()) {
StringBuilder thisToken = new StringBuilder(st.nextToken());
result.append(thisToken.reverse() + " ");
}
String resultString = result.toString();
System.out.println("Reverse String is: "+ resultString);
}
Time Complexity: O(N)
Space Complexity: O(2) as this is not in place reverse.
private String reverseSentence(String sentence)
{
if (sentence == null || sentence.length() < 2)
{
return sentence;
}
String result = "";
String buffer = "";
for (int index = 0; index < sentence.length(); index++)
{
if (sentence.charAt(index) == ' ')
{
result += buffer + ' ';
buffer = "";
}
else
{
buffer = sentence.charAt(index) + buffer;
}
if (index == sentence.length() - 1)
{
result += buffer;
}
}
return result;
}
The time complexity is O(n)
I am getting the first index of space character ' '. Once found I am reversing the word before space char.
I am assuming the string input is "the boy ran" and neglecting @
public class StringOperations {
public static void main(String[] args) {
System.out.println(reverseWords("the boy ran"));
}
/**
* Reverses sentence word by word as mentioned in problem
* @param str sentence to be reversed
* @return reversed sentence
*/
public static String reverseWords(String str) {
if (str == null) {
return str;
} else if (str.length() == 1) {
return str;
}
char[] arr = str.toCharArray();
int prevStart = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == ' ') {
//i-1 cause i is position of space
reverseArr(arr, prevStart, i - 1);
//i+1 cause we will start from char next to space char
prevStart = i + 1;
}
//if the end of sentence reached and there is no space at end
else if(i==arr.length - 1){
reverseArr(arr, prevStart, i);
}
}
return new String(arr);
}
/**
* Reverses char array between the start and end position
* @param arr array to be reversed
* @param start index where we should start
* @param end index where we should end
* @return
*/
public static char[] reverseArr(char[] arr, int start, int end) {
if (arr == null) {
return null;
} else if (arr.length == 1) {
return arr;
}
int loopTill = (end - start + 1) / 2;
for (int i = 0; i < loopTill; i++) {
//swap i and arr.length-i
char tmpChar = arr[start + i];
arr[start + i] = arr[end - i];
arr[end - i] = tmpChar;
}
return arr;
}
}
public class ReverseWords
{
/**
* @param args
*/
public static void main(String[] args)
{
// TODO Auto-generated method stub
ReverseWords reverseWords = new ReverseWords();
System.out.println(reverseWords.swapWords("zhadac"));
System.out.println(reverseWords.reverseWords("the boy ran"));
}
public String reverseWords(String s)
{
StringBuilder sb = new StringBuilder();
String[] strs = s.split("\\s");
for(String str : strs)
{
sb.append(swapWords(str)).append(" ");
}
return sb.toString();
}
public String swapWords(final String s)
{
if(s.length() == 0 || s.length() == 1)
{
return s;
}
StringBuilder sb = new StringBuilder();
sb.append(s.charAt(s.length() - 1));
char start = s.charAt(0);
String rest = swapWords(s.substring(1, s.length() - 1));
sb.append(rest.toCharArray());
sb.append(start);
return sb.toString();
}
}
public class ReverseWords
{
/**
* @param args
*/
public static void main(String[] args)
{
// TODO Auto-generated method stub
ReverseWords reverseWords = new ReverseWords();
System.out.println(reverseWords.swapWords("zhadac"));
System.out.println(reverseWords.reverseWords("the boy ran"));
}
public String reverseWords(String s)
{
StringBuilder sb = new StringBuilder();
String[] strs = s.split("\\s");
for(String str : strs)
{
sb.append(swapWords(str)).append(" ");
}
return sb.toString();
}
public String swapWords(final String s)
{
if(s.length() == 0 || s.length() == 1)
{
return s;
}
StringBuilder sb = new StringBuilder();
sb.append(s.charAt(s.length() - 1));
char start = s.charAt(0);
String rest = swapWords(s.substring(1, s.length() - 1));
sb.append(rest.toCharArray());
sb.append(start);
return sb.toString();
}
}
public static void ReverseWord(ref char[] sentence, int start, int end)
{
for (int index = start, reverse = end; index < end; index++, end--)
{
char temp = sentence[start];
sentence[index] = sentence[reverse];
sentence[reverse] = temp;
}
}
public static void ReverseSentence(char[] sentence)
{
bool started = false;
int beginIndex = -1;
int endIndex = -1;
string temp = string.Empty;
for (int index = 0; index < sentence.Length; index++)
{
if (sentence[index] != ' ' && !started)
{
started = true;
beginIndex = index;
}
else if ((sentence[index] == ' ' && started) || index == sentence.Length - 1)
{
endIndex = index - 1;
ReverseWord(ref sentence, beginIndex, endIndex);
beginIndex = -1;
endIndex = -1;
started = false;
}
}
}
public static String reverseStringByWord(String sentence){
int lastSpace =0;
for(int i =0; i < sentence.length; i++){
if(sentence.charAt(i) == ' '){
reverseString(sentence, lastSpace+1, i-1);
lastSpace = i;
}
}
}
public static void reverseString(String str, start, end){
char temp;
char[] charArr = str.toCharArray();
while(start < end){
temp = charArr[start];
charArr[start] = charArr[end];
charArr[end] = temp;
start++;
end--;
}
str = new String(charArr);
}
Inplace, O(1) memory , O(n) time code in C:
#include <stdio.h>
#include <string.h>
void internal_reverse(char *str){
char c;
int n = strlen(str) , i=0 , j , next;
while(i<n){
if(isspace(str[i])){
++i;
}else{
j = i;
while(j<n && !isspace(str[j])){
++j;
}
next = j--;
while(i<j){
c = str[i];
str[i] = str[j];
str[j] = c;
++i;
--j;
}
i=next;
}
}
}
int main(void) {
char str[100]="the \tboy ran";
printf("Original String : %s\n",str);
internal_reverse(str);
printf("Processed string : %s\n",str);
return 0;
}
Another approach would be to use regex to split and reverse string.Code in python:
import re
def internal_reverse(s):
words = re.split("\s*" , s)
whitespace = re.split("\S*" , s)
out_s = [ words[0][::-1] ]
n = len(words)-1
for i in xrange(n):
out_s.append(whitespace[i+1])
out_s.append(words[i+1][::-1])
return "".join(out_s)
print internal_reverse(str(raw_input()))
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string reverseWords(string str){
string res="";
int n=str.length();
if(n==0) return res;
int i=0;
int start = 0;
int len=0;
string w="";
while(i<n){
if(str[i++]!=' ')
len++;
else if(i<n&&str[i]!=' '){
w=str.substr(start,len);
reverse(w.begin(),w.end());
res=res+w+" ";
start = i;
len=0;
}
}
w=str.substr(start,len);
reverse(w.begin(),w.end());
res=res+w;
return res;
}
A simple c# solution
public static void Main()
{
char[] str = "This is one more example to test approach".ToCharArray();
ReverseStrings(str);
Console.WriteLine(new String(str));
}
public static void ReverseStrings(char[] str)
{
int start = 0;
for (int i = 1; i < str.Length; i++)
{
if (str[i] == ' ')
{
Reverse(str, start, i -1);
start = i+1;
}
}
}
public static void Reverse(char[] array, int start, int end)
{
while (start < end)
{
char temp = array[start];
array[start] = array[end];
array[end] = temp;
start++;
end--;
}
}
Simple in-place O(n) solution in C++:
#include <string>
#include <algorithm>
void reverseWords(std::string &str)
{
int len = str.length();
for (int i = 0; i < len; ++i)
{
int j = i + 1;
// Find the end of the current word
while (j < len && str[j] != ' ')
{
++j;
}
// Reverse the word
for (int start = i, end = j - 1; start < end; ++start, --end)
{
std::swap(str[start], str[end]);
}
i = j;
}
}
Assume the input is a valid input.
public void reverseWords(String input){
int s = 0;
int e = 0;
for(int i=0; i< input.length() ; i++){
if (input.charAt(i) == ' '){
e = i;
String temp = "";
for(int j = s ; j<e ; j++){
temp = input.charAt(j) + temp;
}
s = e;
System.out.print(temp+" ");
}
}
String temp = "";
for(int j = s ; j<input.length() ; j++){
temp = input.charAt(j) + temp;
}
System.out.println(temp);
}
public class ReverseWords {
String reverse(String in) {
int p1 = 0;
int p2 = 0;
char[] input = in.toCharArray();
for(int i = 0; i < input.length; i++){
if(i == input.length -1) {
reverseWord(input, p1, i);
}
if(input[i] == " ".charAt(0)){
p2 = i;
reverseWord(input, p1, p2 - 1);
System.out.println(p1+"/"+p2);
p1 = p2 + 1;
}
}
return String.valueOf(input);
}
void reverseWord(char[] input, int start, int end) {
while(start<=end){
char tmp = input[start];
input[start] = input[end];
input[end] = tmp;
start++;
end--;
}
return;
}
public static void main(String[] args){
long startTime = System.nanoTime();
System.out.println("------------------------------------");
String target = "I love bigg boss";
ReverseWords ana = new ReverseWords();
System.out.println("input : "+ target);
System.out.println("output : " + ana.reverse(target));
System.out.println("------------------------------------");
System.out.println("time taken " + (System.nanoTime() - startTime));
}
}
Time complexity is O(n), and reversal is done in-place.
JavaScript solution:
function reverseString1(str) {
return str.split("").reverse().join("");
}
function reverseString2(str) {
var newString = "";
for (var i = str.length - 1; i >= 0; i--) {
newString += str[i];
}
return newString;
}
function reverseString3(str) {
if (str === "")
return "";
else
return reverseString3(str.substr(1)) + str.charAt(0);
}
function reverseString4(str) {
return (str === '') ? '' : reverseString4(str.substr(1)) + str.charAt(0);
}
function reverseString5(str) {
let strn = "";
for (let char of str) {
strn = char + strn;
}
return strn;
}
function reverseString6(str) {
let revSrring = "";
str.split("").forEach(function (char) {
revSrring = char + revSrring;
});
return revSrring;
}
function reverseString7(str) {
let revSrring = "";
str.split("").forEach(char => revSrring = char + revSrring);
return revSrring;
}
function reverseString8(str) {
return str.split("").reduce(function (revString, char) {
return char + revString;
}, "");
}
function reverseString9(str) {
return str.split("").reduce((revString, char) => char + revString, "");
}
function reverseString10(str) {
return [...str].reduce((accumulator, current) => current + accumulator)
}
function reverseString11(str) {
return str.split('').sort(() => 1).join('');
}
let inputString = 'the boy ran'
console.log(inputString.split(' ').map(value => reverseString1(value)))
console.log(inputString.split(' ').map(value => reverseString2(value)))
console.log(inputString.split(' ').map(value => reverseString3(value)))
console.log(inputString.split(' ').map(value => reverseString4(value)))
console.log(inputString.split(' ').map(value => reverseString5(value)))
console.log(inputString.split(' ').map(value => reverseString6(value)))
console.log(inputString.split(' ').map(value => reverseString7(value)))
console.log(inputString.split(' ').map(value => reverseString8(value)))
console.log(inputString.split(' ').map(value => reverseString9(value)))
console.log(inputString.split(' ').map(value => reverseString10(value)))
console.log(inputString.split(' ').map(value => reverseString11(value)))
string reverseWords(string str){
stringstream wholeWord;
stringstream currentWord;
for (char c : str) {
if (c != ' ') {
currentWord << c;
}
else {
string currentWordAsStr = currentWord.str();
reverse(currentWordAsStr.begin(), currentWordAsStr.end());
wholeWord << currentWordAsStr;
wholeWord << c;
currentWord.str(string());
}
}
string currentWordAsStr = currentWord.str();
reverse(currentWordAsStr.begin(), currentWordAsStr.end());
wholeWord << currentWordAsStr;
return wholeWord.str();
}}
something like
string input = @"The boy run";
StringBuilder builder = new StringBuilder();
int i =0;
string temp;
bool isFirstInsert = true;
while(i< input.length)
{
while(input[i] != ' ' && i< input.length)
{
temp= input[i++].ToString() + temp;
}
if(! isFirstInsert)
{
builder.append(" ");
}
builder.append(temp);
temp =string.Empty;
}
string output = builder.ToString();
order will be O(n) yes it has space complicity.
/*Using StringBuffer we can easily do this in java */
import java.util.Scanner;
public class WordReverse {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String inp = in.nextLine();
String[] inpArray =inp.split(" ");
StringBuilder sb = new StringBuilder();
for(int i=inpArray.length-1;i>=0;i--){
sb.append(" ").append(inpArray[i]);
}
System.out.println(sb.reverse());
}
- Satveer Singh June 06, 2014