Sunday, July 29, 2007

Reversing words in a String

This I think is by far most popular string Interview question, be it on Java/C/C++ or C#
Question : Write procedure to reverse the words in a String, assume words are separated by blank-spaces e.g. given a string "Writing and debugging software", the output of the procedure should be "software debugging and Writing"

Here is the code which i had written recently in Java, i think the code and algorithm is self-explanatory, but if you need help understanding the code please let me know.

If you have a big string and don't like the idea of O(n) space complexity and want to do it in O(1) space, than instead of putting words in word and to_ret arrays, you just store the array indexes and as soon as you find a blank space shift the original array up by the last word length and add the word to appropriate position in the string. This is just a hint i'll leave the implementation to you.. I can send you the code, if needed.


public class Reverse {
public static String reverse(String str) {
char[] chars = str.toCharArray();
char[] to_ret = new char[chars.length];
char[] word = new char[chars.length];
int l = 0;
int last = chars.length - 1;
for (int i = 0; i < chars.length; i++) {
if (chars[i] == ' ') {
for (; l > 0; l--) {
to_ret[last] = word[l - 1];
last--;
}
to_ret[last] = ' ';
last--;
l = 0;
} else {
word[l] = chars[i];
l++;
}
}
//add the last word if any
if (l != 0) {
for (; l > 0; l--) {
to_ret[last] = word[l - 1];
last--;
}
}
return new String(to_ret);
}

public static void main(String[] args) {
String str = "This is a beautiful World";
System.out.println(str);
System.out.println(reverse(str));
}
}

No comments: