Reverse String in Java
$begingroup$
I've been revamping on my coding puzzles practices. What is the complexity (both time and space) for this method:
public static String reverse(String word) {
if (word == null || "".equals(word) || word.length() == 1) {
throw new IllegalArgumentException("Invalid Entry");
}
StringBuilder result = new StringBuilder();
for (int i=word.length() - 1; i >= 0; i--) {
result.append(word.charAt(i));
}
return result.toString();
}
Is this a more optimized solution (what is the time and space complexity of this one as well):
public static String reverse ( String s ) {
int length = s.length(), last = length - 1;
char chars = s.toCharArray();
for ( int i = 0; i < length/2; i++ ) {
char c = chars[i];
chars[i] = chars[last - i];
chars[last - i] = c;
}
return new String(chars);
}
I know that there might be duplicate questions similar to this but am not asking for a solution. I'm only seeking how to figure out the two different types of complexities.
java complexity
$endgroup$
add a comment |
$begingroup$
I've been revamping on my coding puzzles practices. What is the complexity (both time and space) for this method:
public static String reverse(String word) {
if (word == null || "".equals(word) || word.length() == 1) {
throw new IllegalArgumentException("Invalid Entry");
}
StringBuilder result = new StringBuilder();
for (int i=word.length() - 1; i >= 0; i--) {
result.append(word.charAt(i));
}
return result.toString();
}
Is this a more optimized solution (what is the time and space complexity of this one as well):
public static String reverse ( String s ) {
int length = s.length(), last = length - 1;
char chars = s.toCharArray();
for ( int i = 0; i < length/2; i++ ) {
char c = chars[i];
chars[i] = chars[last - i];
chars[last - i] = c;
}
return new String(chars);
}
I know that there might be duplicate questions similar to this but am not asking for a solution. I'm only seeking how to figure out the two different types of complexities.
java complexity
$endgroup$
add a comment |
$begingroup$
I've been revamping on my coding puzzles practices. What is the complexity (both time and space) for this method:
public static String reverse(String word) {
if (word == null || "".equals(word) || word.length() == 1) {
throw new IllegalArgumentException("Invalid Entry");
}
StringBuilder result = new StringBuilder();
for (int i=word.length() - 1; i >= 0; i--) {
result.append(word.charAt(i));
}
return result.toString();
}
Is this a more optimized solution (what is the time and space complexity of this one as well):
public static String reverse ( String s ) {
int length = s.length(), last = length - 1;
char chars = s.toCharArray();
for ( int i = 0; i < length/2; i++ ) {
char c = chars[i];
chars[i] = chars[last - i];
chars[last - i] = c;
}
return new String(chars);
}
I know that there might be duplicate questions similar to this but am not asking for a solution. I'm only seeking how to figure out the two different types of complexities.
java complexity
$endgroup$
I've been revamping on my coding puzzles practices. What is the complexity (both time and space) for this method:
public static String reverse(String word) {
if (word == null || "".equals(word) || word.length() == 1) {
throw new IllegalArgumentException("Invalid Entry");
}
StringBuilder result = new StringBuilder();
for (int i=word.length() - 1; i >= 0; i--) {
result.append(word.charAt(i));
}
return result.toString();
}
Is this a more optimized solution (what is the time and space complexity of this one as well):
public static String reverse ( String s ) {
int length = s.length(), last = length - 1;
char chars = s.toCharArray();
for ( int i = 0; i < length/2; i++ ) {
char c = chars[i];
chars[i] = chars[last - i];
chars[last - i] = c;
}
return new String(chars);
}
I know that there might be duplicate questions similar to this but am not asking for a solution. I'm only seeking how to figure out the two different types of complexities.
java complexity
java complexity
edited 10 mins ago
Jamal♦
30.3k11119227
30.3k11119227
asked 5 hours ago
PacificNW_LoverPacificNW_Lover
15616
15616
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Linear in space
Both are linear in space.
The first one is linear because the StringBuilder
makes a copy of the string.
The second one is linear because toCharArray
makes a copy of the string. We know it can't use the backing array of the string, because the string is immutable. Clearly you can modify the character array. We can ignore the swap variable (c
), as it is either constant space or
We can consider a Java compiler (even if none currently work this way) that would release the backing array to the toCharArray
, but we can't guarantee that. Because the calling code may want to use the string after calling this method. So the assumption in the method is that we are creating a new array.
If the input is a string and the output is a different string (and we can't change the original string, so it has to be different), then linear time is the best we could possibly do. So even without the intermediate variable, these would still be linear in space. Both create new strings.
Linear in time
Both are linear in time.
The first one does $n$ iterations with one append
operation per iteration. The append
operations should be constant time. There may be occasional copy operations that can be amortized to be constant time per append
operation or linear time overall. That's $mathcal{O}(n)$.
The second one does $frac{n}{2}$ iterations with two array assignments per iteration. That's also linear, $mathcal{O}(n)$. Because $frac{n}{2}$ grows linearly with $n$ and two is a constant.
Constant space
To have a method be constant in space, it needs to return the same memory that brings the input. E.g.
public void reverse(char chars) {
for (int i = 0, j = chars.length - 1; i < j; i++, j--) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}
This is constant in space and linear in time. But it neither takes nor returns a string.
Constant space and time
There's a sort of backwards way of reversing a string in constant time and space.
class ReversedString {
private String string;
public ReversedString(String string) {
this.string = string;
}
public char charAt(int index) {
return string.charAt(string.length() - 1 - index);
}
}
But we wouldn't be able to just use this as a string without creating a new string. The only operation that works (so far) is charAt
. We might be able to make other operations work, but not all of them. In particular, a toString
would be linear in time and space, just like the original methods. Because it would have to make a new string of the same length.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f214084%2freverse-string-in-java%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Linear in space
Both are linear in space.
The first one is linear because the StringBuilder
makes a copy of the string.
The second one is linear because toCharArray
makes a copy of the string. We know it can't use the backing array of the string, because the string is immutable. Clearly you can modify the character array. We can ignore the swap variable (c
), as it is either constant space or
We can consider a Java compiler (even if none currently work this way) that would release the backing array to the toCharArray
, but we can't guarantee that. Because the calling code may want to use the string after calling this method. So the assumption in the method is that we are creating a new array.
If the input is a string and the output is a different string (and we can't change the original string, so it has to be different), then linear time is the best we could possibly do. So even without the intermediate variable, these would still be linear in space. Both create new strings.
Linear in time
Both are linear in time.
The first one does $n$ iterations with one append
operation per iteration. The append
operations should be constant time. There may be occasional copy operations that can be amortized to be constant time per append
operation or linear time overall. That's $mathcal{O}(n)$.
The second one does $frac{n}{2}$ iterations with two array assignments per iteration. That's also linear, $mathcal{O}(n)$. Because $frac{n}{2}$ grows linearly with $n$ and two is a constant.
Constant space
To have a method be constant in space, it needs to return the same memory that brings the input. E.g.
public void reverse(char chars) {
for (int i = 0, j = chars.length - 1; i < j; i++, j--) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}
This is constant in space and linear in time. But it neither takes nor returns a string.
Constant space and time
There's a sort of backwards way of reversing a string in constant time and space.
class ReversedString {
private String string;
public ReversedString(String string) {
this.string = string;
}
public char charAt(int index) {
return string.charAt(string.length() - 1 - index);
}
}
But we wouldn't be able to just use this as a string without creating a new string. The only operation that works (so far) is charAt
. We might be able to make other operations work, but not all of them. In particular, a toString
would be linear in time and space, just like the original methods. Because it would have to make a new string of the same length.
$endgroup$
add a comment |
$begingroup$
Linear in space
Both are linear in space.
The first one is linear because the StringBuilder
makes a copy of the string.
The second one is linear because toCharArray
makes a copy of the string. We know it can't use the backing array of the string, because the string is immutable. Clearly you can modify the character array. We can ignore the swap variable (c
), as it is either constant space or
We can consider a Java compiler (even if none currently work this way) that would release the backing array to the toCharArray
, but we can't guarantee that. Because the calling code may want to use the string after calling this method. So the assumption in the method is that we are creating a new array.
If the input is a string and the output is a different string (and we can't change the original string, so it has to be different), then linear time is the best we could possibly do. So even without the intermediate variable, these would still be linear in space. Both create new strings.
Linear in time
Both are linear in time.
The first one does $n$ iterations with one append
operation per iteration. The append
operations should be constant time. There may be occasional copy operations that can be amortized to be constant time per append
operation or linear time overall. That's $mathcal{O}(n)$.
The second one does $frac{n}{2}$ iterations with two array assignments per iteration. That's also linear, $mathcal{O}(n)$. Because $frac{n}{2}$ grows linearly with $n$ and two is a constant.
Constant space
To have a method be constant in space, it needs to return the same memory that brings the input. E.g.
public void reverse(char chars) {
for (int i = 0, j = chars.length - 1; i < j; i++, j--) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}
This is constant in space and linear in time. But it neither takes nor returns a string.
Constant space and time
There's a sort of backwards way of reversing a string in constant time and space.
class ReversedString {
private String string;
public ReversedString(String string) {
this.string = string;
}
public char charAt(int index) {
return string.charAt(string.length() - 1 - index);
}
}
But we wouldn't be able to just use this as a string without creating a new string. The only operation that works (so far) is charAt
. We might be able to make other operations work, but not all of them. In particular, a toString
would be linear in time and space, just like the original methods. Because it would have to make a new string of the same length.
$endgroup$
add a comment |
$begingroup$
Linear in space
Both are linear in space.
The first one is linear because the StringBuilder
makes a copy of the string.
The second one is linear because toCharArray
makes a copy of the string. We know it can't use the backing array of the string, because the string is immutable. Clearly you can modify the character array. We can ignore the swap variable (c
), as it is either constant space or
We can consider a Java compiler (even if none currently work this way) that would release the backing array to the toCharArray
, but we can't guarantee that. Because the calling code may want to use the string after calling this method. So the assumption in the method is that we are creating a new array.
If the input is a string and the output is a different string (and we can't change the original string, so it has to be different), then linear time is the best we could possibly do. So even without the intermediate variable, these would still be linear in space. Both create new strings.
Linear in time
Both are linear in time.
The first one does $n$ iterations with one append
operation per iteration. The append
operations should be constant time. There may be occasional copy operations that can be amortized to be constant time per append
operation or linear time overall. That's $mathcal{O}(n)$.
The second one does $frac{n}{2}$ iterations with two array assignments per iteration. That's also linear, $mathcal{O}(n)$. Because $frac{n}{2}$ grows linearly with $n$ and two is a constant.
Constant space
To have a method be constant in space, it needs to return the same memory that brings the input. E.g.
public void reverse(char chars) {
for (int i = 0, j = chars.length - 1; i < j; i++, j--) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}
This is constant in space and linear in time. But it neither takes nor returns a string.
Constant space and time
There's a sort of backwards way of reversing a string in constant time and space.
class ReversedString {
private String string;
public ReversedString(String string) {
this.string = string;
}
public char charAt(int index) {
return string.charAt(string.length() - 1 - index);
}
}
But we wouldn't be able to just use this as a string without creating a new string. The only operation that works (so far) is charAt
. We might be able to make other operations work, but not all of them. In particular, a toString
would be linear in time and space, just like the original methods. Because it would have to make a new string of the same length.
$endgroup$
Linear in space
Both are linear in space.
The first one is linear because the StringBuilder
makes a copy of the string.
The second one is linear because toCharArray
makes a copy of the string. We know it can't use the backing array of the string, because the string is immutable. Clearly you can modify the character array. We can ignore the swap variable (c
), as it is either constant space or
We can consider a Java compiler (even if none currently work this way) that would release the backing array to the toCharArray
, but we can't guarantee that. Because the calling code may want to use the string after calling this method. So the assumption in the method is that we are creating a new array.
If the input is a string and the output is a different string (and we can't change the original string, so it has to be different), then linear time is the best we could possibly do. So even without the intermediate variable, these would still be linear in space. Both create new strings.
Linear in time
Both are linear in time.
The first one does $n$ iterations with one append
operation per iteration. The append
operations should be constant time. There may be occasional copy operations that can be amortized to be constant time per append
operation or linear time overall. That's $mathcal{O}(n)$.
The second one does $frac{n}{2}$ iterations with two array assignments per iteration. That's also linear, $mathcal{O}(n)$. Because $frac{n}{2}$ grows linearly with $n$ and two is a constant.
Constant space
To have a method be constant in space, it needs to return the same memory that brings the input. E.g.
public void reverse(char chars) {
for (int i = 0, j = chars.length - 1; i < j; i++, j--) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}
This is constant in space and linear in time. But it neither takes nor returns a string.
Constant space and time
There's a sort of backwards way of reversing a string in constant time and space.
class ReversedString {
private String string;
public ReversedString(String string) {
this.string = string;
}
public char charAt(int index) {
return string.charAt(string.length() - 1 - index);
}
}
But we wouldn't be able to just use this as a string without creating a new string. The only operation that works (so far) is charAt
. We might be able to make other operations work, but not all of them. In particular, a toString
would be linear in time and space, just like the original methods. Because it would have to make a new string of the same length.
answered 2 hours ago
mdfst13mdfst13
17.8k62157
17.8k62157
add a comment |
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f214084%2freverse-string-in-java%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown