I had to resolve a problem for an interview, and i didn't understood something. The problem was, for a string like "we like hiking" to reverse the string like this: "ew ekil gnikih", this means, to explode the string like: str.split(" ") and then, each word to reverse and to add to the new string.
The problem was at the end of the problem, because was asking something about Complexity, like: " - expected worst-case time complexity is O(N)" - expected wors-case space complexity is O(N) (not counting the storage required for input arguments)
I resolved the problem like this:
public static String solution(String S){
if(S.length()>1 && S.length()<200000){
String toReturn = "";
String[] splitted = null;
if(S.contains(" ")){
splitted = S.split(" ");
}
else{
splitted = new String[]{S};
}
for(int i=0;i<=splitted.length-1;i++){
String wordToChange = splitted[i];
String reversedWord = "";
for(int j=wordToChange.length()-1;j>=0;j--)
reversedWord+=wordToChange.charAt(j);
toReturn+=" " + reversedWord;
}
return toReturn.trim();
}
return null;
}
What i should do about the complexity request? Thanks!
I think this is not the correct answer for at least the time complexity.
In my opinion the splitting of a String will most likely be a complexity of O(n). And it'll just add to next complexity, therefore we can forget about it.
Now you're creating an empty String and concatenating a char on top of each String. Here you're assuming this operation is as cheap like inserting a value into an array (O(1)).
In this case you should assume, that you're creating a new String each time with the member method concat(). If you're have the chance of looking into the implementation of String.concat(String) you'll see that this method is creating another char[] in the length of string1.length + string2.length and is copying both string1 and string2 into it. So this method alone has a complexity of O(n).
Because you're concatenating n chars for one word of n length, it has the complexity of O(n * (n / 2)) = O(n^2) for one word. Assuming the worst case of just one word, you have the complexity class of O(n^2).
I would concur with the space complexity class of O(n) for your code. But this is just under the assumption of the intelligence of the JVM reusing you're unused space.
Your code should work, but I think it is really not good code for this problem. You can improve it with a StringBuilder or direct operations on a char[].
The StringBuilder is a good idea, because it acts similar to a Vector or a ArrayList. I has a much bigger char[] working in its background than a String. If it's capacity is exceeded (by using the append() method), it will create a much bigger array, something like 2 time the size of the previous backing array. This might only be a time complexity of O(nlogn). But you can tweak it furthermore by initializing the StringBuilder with a capacity of the same size as your initial String. This means the backing char[] will not be copied at all, because you'll not exceed it's capacity.
Here is an example with the use of a char[]:
private static void reverseCharArray(char[] result, int start, int end) {
int halfDifference = (end - start) / 2;
for (int i = 0; i < halfDifference; i++) {
char buffer = result[start + i];
result[start + i] = result[end - i - 1];
result[end - i - 1] = buffer;
}
}
public static String reverseWordInString(String string) {
char[] stringAsCharArray = string.toCharArray();
int indexStart = 0;
for (int indexEnd = 0; indexEnd < stringAsCharArray.length; indexEnd++) {
if (stringAsCharArray[indexEnd] != ' ') {
continue;
}
StringOperations.reverseCharArray(stringAsCharArray, indexStart, indexEnd);
indexStart = indexEnd + 1;
}
StringOperations.reverseCharArray(stringAsCharArray, indexStart, stringAsCharArray.length);
return String.valueOf(stringAsCharArray);
}