使用堆栈 Java 反转字符串

Question

问题的标题已经说明了一切。我正在尝试解决这个问题，但我没有成功。 问题如下：

给定一个字符串S，任务是使用堆栈反转该字符串。

示例1：

输入：S=“GeeksforGeeks” 输出：skeeGrofskeeG

您的任务： 您不需要读取输入或打印任何内容。你的任务是完成函数reverse()，它将字符串S作为输入参数并返回反转后的字符串。

预期时间复杂度：O(N) 预期辅助空间：O(N)

我的代码：

class Solution {
    Stack<Character> s1=new Stack<Character>();
    Stack<Character> s2=new Stack<Character>();
    
    public String reverse(String S){
        String temp="";
        //code here
        for(int i=0;i<S.length();i++){
            s1.push(S.charAt(i));   
        }
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        while(!s2.isEmpty()){
            temp=temp+s2.pop();
        }
        return temp;
    }

}

我的所有测试用例都失败了。帮助将不胜感激！

Answer 1

您的代码的问题是您使用了两个堆栈（

s1

和

s2

），这对于这个问题来说是不必要的。堆栈反转字符串的目的是利用其后进先出 (LIFO) 属性。当您将字符串的字符压入堆栈然后弹出它们时，它们会以相反的顺序出现。因此，单个堆栈足以实现所需的结果。

以下是修改代码的方法：

1. 将字符串

   S

   的每个字符压入堆栈。
2. 从堆栈中弹出每个字符并将其附加到结果字符串中。

这将反转字符串，因为每个字符都按照与推送顺序相反的顺序弹出。

这是您的代码的修订版本：

class Solution {
    Stack<Character> stack = new Stack<Character>();

    public String reverse(String S){
        String result = "";

        // Push each character onto the stack
        for(int i = 0; i < S.length(); i++){
            stack.push(S.charAt(i));
        }

        // Pop each character from the stack and append to result
        while(!stack.isEmpty()){
            result += stack.pop();
        }

        return result;
    }
}

此修订版本应该可以正常工作并通过测试用例，因为它正确实现了堆栈来反转字符串。