反转字符串

需求描述

Write a Java Program to reverse a string without using String inbuilt funciton reverse().

解决方案

在Java中，字符串是不可变的。因此，我们无法直接在原字符串上进行操作，反转字符串通常需要新建一个字符串或者使用其他数据结构，例如字符数组、StringBuilder等。以下是一些不同的实现方法：

方法一：使用字符数组

public class Main {
    public static void main(String[] args) {
        String input = "Hello, World!";
        char[] chars = input.toCharArray();  // 将字符串转换为字符数组
        String output = "";
        for(int i=chars.length-1; i>=0; i--) {  // 从后向前遍历字符数组
            output += chars[i];  // 将字符添加到输出字符串中
        }
        System.out.println(output);
    }
}

这段代码的核心思想是将输入字符串转换为字符数组，然后从后向前遍历字符数组，将每个字符添加到输出字符串中。这样，我们就可以得到反转后的字符串。

时间复杂度：O(n)，其中 n 为字符串的长度。这是因为我们需要遍历整个字符数组一次。

空间复杂度：O(n)。首先，我们需要 O(n) 的空间来存储字符数组。然后，我们还需要 O(n) 的空间来存储输出的字符串。因此，总的空间复杂度为 O(n)。

方法二：使用StringBuilder

public class Main {
    public static void main(String[] args) {
        String input = "Hello, World!";
        StringBuilder sb = new StringBuilder(input);  // 使用StringBuilder包装输入字符串
        sb.reverse();  // 反转StringBuilder
        String output = sb.toString();  // 将StringBuilder转换为字符串
        System.out.println(output);
    }
}

这段代码使用了Java的StringBuilder类，它是一个可变的字符序列。我们先用StringBuilder包装输入字符串，然后调用StringBuilder的reverse方法反转字符序列，最后将反转后的StringBuilder转换为字符串。

时间复杂度：StringBuilder 的 reverse() 方法的时间复杂度为 O(n)，其中 n 为字符串的长度。

空间复杂度：StringBuilder 的空间复杂度为 O(n)。这是因为 StringBuilder 在内部使用了字符数组来存储字符串。因此，它需要 O(n) 的空间来存储字符串。

方法三：使用递归

public class Main {
    public static void main(String[] args) {
        String input = "Hello, World!";
        String output = reverse(input);
        System.out.println(output);
    }

    public static String reverse(String s) {
        if (s.isEmpty())  // 如果字符串为空，则直接返回
            return s;
        return reverse(s.substring(1)) + s.charAt(0);  // 使用递归反转字符串
    }
}

这段代码使用了递归的方法反转字符串。我们先检查字符串是否为空，如果为空，则直接返回。否则，我们将字符串的第一个字符放到最后，然后递归地反转剩下的字符串。

时间复杂度：O(n^2)，其中 n 为字符串的长度。这是因为每次递归调用都会生成一个新的字符串，这需要 O(n) 的时间，而我们需要递归 n 次，所以总的时间复杂度为 O(n^2)。

空间复杂度：O(n)。递归的深度为 n，所以需要 O(n) 的栈空间。另外，每次递归调用都会生成一个新的字符串，这需要 O(n) 的空间。因此，总的空间复杂度为 O(n)。