Reverse String in Java












-1












$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.










share|improve this question











$endgroup$

















    -1












    $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.










    share|improve this question











    $endgroup$















      -1












      -1








      -1





      $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.










      share|improve this question











      $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






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited 10 mins ago









      Jamal

      30.3k11119227




      30.3k11119227










      asked 5 hours ago









      PacificNW_LoverPacificNW_Lover

      15616




      15616






















          1 Answer
          1






          active

          oldest

          votes


















          0












          $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.






          share|improve this answer









          $endgroup$













            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
            });


            }
            });














            draft saved

            draft discarded


















            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









            0












            $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.






            share|improve this answer









            $endgroup$


















              0












              $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.






              share|improve this answer









              $endgroup$
















                0












                0








                0





                $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.






                share|improve this answer









                $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.







                share|improve this answer












                share|improve this answer



                share|improve this answer










                answered 2 hours ago









                mdfst13mdfst13

                17.8k62157




                17.8k62157






























                    draft saved

                    draft discarded




















































                    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.




                    draft saved


                    draft discarded














                    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





















































                    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







                    Popular posts from this blog

                    Сан-Квентин

                    Алькесар

                    Josef Freinademetz