刷题_20：字符串反转 and 公共子串计算

太过爱你忘了你带给我的痛 2023-09-30 21:13 2阅读 0赞

### 一.字符串反转 ###

**题目链接：**

> [字符串反转][Link 1]

**题目描述：**

> **接受一个只包含小写字母的字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）**

**输入描述：**

> **输入一行，为一个只包含小写字母的字符串。**

**输出描述：**

> **输出该字符串反转后的字符串。**

**示例1：**

> **输入：  
> abcd  
> 输出：  
> dcba**

**个人总结：**

> **将输入的字符串转成字符数组，然后定义一个左下标 l 和右下标 r ，交换二者，然后 l++ ， r-- 一直到 l>=r 即可，说白了就是反转一个数组。**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            String s = sc.nextLine();
            System.out.println(reverse(s));
        }
    
        public static String reverse(String s) {
        
            char[] chs = s.toCharArray();
            int l = 0;
            int r = chs.length - 1;
            while (l < r) {
        
                char tmp = chs[l];
                chs[l] = chs[r];
                chs[r] = tmp;
                l++;
                r--;
            }
            return String.valueOf(chs);
        }
    }

--------------------

### 二.公共子串计算 ###

**题目链接：**

> [公共子串计算][Link 2]

**题目描述：**

> **给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。  
> 注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。  
> 数据范围：字符串长度：1≤s≤150  
> 进阶：时间复杂度：O(n^3) ，空间复杂度：O(n)**

**输入描述：**

> **输入两个只包含小写字母的字符串**

**输出描述：**

> **输出一个整数，代表最大公共子串的长度**

**示例1：**

> **输入：  
> asdfas  
> werasdfaswer  
> 输出：  
> 6**

**个人总结：**

> **不能说毫不相干，只能说一模一样[查找两个字符串a,b中的最长公共子串][a_b]**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            String s = sc.nextLine();
            String p = sc.nextLine();
            System.out.println(getMaxLen(s, p));
        }
    
        //获取最大公共子串长度
        public static int getMaxLen(String s, String p) {
        
            int max = 0;
            int lenS = s.length();
            int lenP = p.length();
            //dp[i][j]：以i - 1为结尾的s子串和以j - 1为结尾的p子串的最大公共子串的长度
            int[][] dp = new int[lenS + 1][lenP + 1];
            for (int i = 1; i <= lenS; i++) {
        
                for (int j = 1; j <= lenP; j++) {
        
                    if (s.charAt(i - 1) == p.charAt(j - 1)) {
        
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                        max = Math.max(max, dp[i][j]);
                    } else {
        
                        dp[i][j] = 0;
                    }
                }
            }
            return max;
        }
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/e45e078701ab4e4cb49393ae30f1bb04
[Link 2]: https://www.nowcoder.com/questionTerminal/98dc82c094e043ccb7e0570e5342dd1b
[a_b]: https://blog.csdn.net/qq_53130059/article/details/129786239?spm=1001.2014.3001.5501