leetcode 344. 反转字符串递归写法

水深无声 2024-05-06 09:41 57阅读 0赞

#### 文章目录 ####

*   *  题目
 *  
 *  
 *   *  一般写法
     *  优化一
     *  优化二
     *  优化三
     *  测试结果

### 题目 ###

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
    输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
    输出：["h","a","n","n","a","H"]

提示：

1 <= s.length <= 105
    s[i]

都是 ASCII 码表中的可打印字符

来源：力扣（LeetCode）

题目理解：

我们给出了一个需要使用递归方法反转的句子。通过反转，我们的意思是从右到左的字符互换，即将第 (i) 个字符与第 (ni) 个字符互换，其中 n 是给定字符串的长度。

例子

**输入:** coding is awesome.

**输出:** emosewa si gnidoc

**输入:** Recursion is easy  
**输出:** ysae si noisruceR

##  ##

递归算法  
解决这个问题的一个简单方法是通过简单的迭代，只需使用一个 for 循环，i 从索引 0 到 n/2，然后与 ni 进行字符交换。但是在这里，我们将使用递归来研究问题的解决方案。

由于使用递归的解决方案涉及用一个或更小的问题来表示问题的想法。它主要由三个主要内容组成：

归纳假设。

基础条件。

假设假设正确，生成解决方案。

归纳假设：假设我们有一个长度为 n 的字符串，假设 reverseFunction() 是将字符串作为输入并返回与输入字符串相反的字符串的函数。

基本条件：当 n=0 或 n=1（空字符串）时，仅返回输入字符串。由于单个字符或空字符串的反转只是它本身。

生成解决方案：现在我们需要计算长度为 n 的字符串的倒数，我们得到长度为 n-1 的字符串的倒数。因此，长度为 n 的字符串的反转将是长度为 n-1 的字符串的反转，最后附加了附加字符。

例子-对于长度为 n 的字符串 s，Rev(s,i) 将返回从索引 i 到 n 的反向字符串。Rev(s,0) = Rev(s,1)+s\[0\]。假设 s=”APPLE” Rev(s,0) = “ELPPA”，而 Rev(s,1) = “ELPP” 和 s\[0\]=”A”。因此 Rev(s,0) == rev(s,1) +s\[0\]。

令 F(s,0) 为反函数。其中 s=”APPLE”，n=5。F(s,0) => F(s,1)+”A”。=> “ELPP” + “A” = “ELPPA”。F(s,1) => F(s,2) + “P” => “ELP”+”P” = “ELPP” F(s,2) => F(s,3) + “P” = > “EL” + “P” = “ELP” F(s,3) => F(s,4) + “L” => “E”+”L” = “EL” F(s,4) = > F(s,5) + “E” => “E”。

##  ##

Java 实现

### 一般写法 ###

该算法涉及使用递归反向函数，该函数对上述归纳假设和递归起作用。它基本上使用字符串的子字符串函数，并在每个递归调用中连接字符串。

import java.util.*;
    public class Main
    {
        
        static String reverseFunction(String s){
        
            if( s.length()==0 ){
        
                return new String();                        
            }
            // 递归调用
            return reverseFunction(s.substring(1)) + s.charAt(0);       
        }
        
    //测试代码并输入测试值
    	public static void main(String[] args) {
        
    		Scanner sc = new Scanner(System.in);
    		//测试次数
    		int n = sc.nextInt();
    		sc.nextLine();
    		while(n-->0){
        
    		System.out.print("Input: ");
    		String s = sc.nextLine();
    		System.out.print("Output: ");
    		System.out.println(reverseFunction(s));
    		
    		}
    	}
    }

注意：由于 java 中的字符串是完全不可变的，每次我们在每次递归调用中附加解决方案字符串时，java 都会在内部生成一个包含连接字符串内容的新字符串。这将最坏情况的时间复杂度从 O(n) 增加到 O(n^2)，其中 n 是输入字符串的长度。

### 优化一 ###

上述问题的一种解决方案是使用可变的Java 内置字符串类，即StringBuilder，它在O(1) 时间内剪切/附加字符串。因此，使用时间复杂度 O(n) 的StringBuilder类的java 代码如下：

import java.util.*;
    public class Main
    {
        
        static StringBuilder reverseFunction(String s){
        
            if( s.length()==0 ){
        
                return new StringBuilder();          
            }
            // 递归调用
            return reverseFunction(s.substring(1)).append(s.charAt(0));     
        }
    
    //测试代码并输入测试值
    
    	public static void main(String[] args) {
        
    		Scanner sc = new Scanner(System.in);
    		//测试次数
    		int n = sc.nextInt();
    		sc.nextLine();
    		while(n-->0){
        
    		System.out.print("输入: ");
    		String s = sc.nextLine();
    		System.out.print("输出: ");
    		System.out.println(reverseFunction(s));
    		
    		}
    	}
    }
    
    输出: -
    2
    输入: Hello World!
    输出: !dlroW olleH
    输入: Reverse it.
    输出: .ti esreveR

### 优化二 ###

避免在每次递归调用中连接字符串的另一个更好的解决方案/算法是使用另一个参数，该参数将输入 i 作为整数，以便函数将从索引 i 开始到字符串末尾的字符串反转。

下面给出了 Java 代码：

import java.util.*;
    public class Main
    {
        
        static String reverseFunction(String s, int i){
        
            if(i==s.length()){
        
                return "";                               		
            }
            // 递归调用
            return reverseFunction(s,i+1)+s.charAt(i);   
        }
    
    
    //测试代码并输入测试值
    
    	public static void main(String[] args) {
        
    		Scanner sc = new Scanner(System.in);
    		//测试次数
    		int n = sc.nextInt();
    		sc.nextLine();
    		while(n-->0){
        
    		System.out.print("输入: ");
    		String s = sc.nextLine();
    		System.out.print("输出: ");
    		System.out.println(reverseFunction(s,0));
    		}
    	}
    }

### 优化三 ###

复杂性可以通过在递归调用中使用 StringBuilder 类来附加字符来进一步提高，因为使用字符串会在每个递归调用中创建一个新字符串。下面给出了它的实现。

import java.util.*;
    public class Main
    {
        
        static StringBuilder reverseFunction(String s, int i){
        
            if( i == s.length() ){
        
                return new StringBuilder();
            }
            // 递归调用
            return reverseFunction(s,i+1).append(s.charAt(i));
        }
    //测试代码并输入测试值
    	public static void main(String[] args) {
        
    		Scanner sc = new Scanner(System.in);
    		//测试次数
    		int n = sc.nextInt();
    		sc.nextLine();
    		while(n-->0){
        
    		System.out.print("输入: ");
    		String s = sc.nextLine();
    		System.out.print("输出: ");
    		System.out.println(reverseFunction(s,0));
    		}
    
    		}
    	}
    }

### 测试结果 ###

![在这里插入图片描述][b9cb98ec15744b1b8ce039b25669e415.png]  
时间复杂度O(n) 空间复杂度O(1)

欢迎评论 虎年大吉！

[b9cb98ec15744b1b8ce039b25669e415.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/89ee46fcee5a4a8a9abc7fc49eeb47ae.png