Java题目训练——字符串反转和公共子串计算

雨点打透心脏的1/2处 2023-09-30 21:43 3阅读 0赞

**目录**

一、字符串反转

二、公共子串计算

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

### 一、字符串反转 ###

题目描述：

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

输入描述：

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

输出描述：

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

示例

> 示例1
> 
> 输入：abcd
> 
> 输出：dcba

**题目解析：**

> 本题是一道很经典的题目，有很多种方式，这里我选择新建一个StringBuilder的字符串sb，然后从后往前遍历初始字符串，利用StringBuilder的append方法，就元素按遍历顺序加入，最好返回sb字符串，实现字符串反转。

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            String s = scanner.nextLine();
            if(s.length() == 0){
                return;
            }
            System.out.println(res(s));
        }
    
        public static String res(String s){
            StringBuilder sb = new StringBuilder();
            for (int i = s.length() - 1; i >= 0; i--) {
                sb.append(s.charAt(i));
            }
            return sb.toString();
        }
    }

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

题目描述：

给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。

> 注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。
> 
> 数据范围：字符串长度：1<=s<=150
> 
> 进阶：时间复杂度：O(![n^\{3\}][n_3]) ，空间复杂度：O(n)

输入描述：

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

输出描述：

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

示例

> 示例1
> 
> 输入：asdfas
> 
> werasdfaswer
> 
> 输出：6

**题目解析：**

这道和求最长公共子串的思路基本一样，但是还是有细节问题不一样，有兴趣可以参考：

这里介绍三种思路：

1. 动态规划（推荐）

> (1). 创立状态数组arr = new int\[s1.length() + 1\]\[s2.length() + 1\]。
> 
> (2). 寻找状态方程：如果此时位置的字符相同（s1.charAt(i - 1) == s2.charAt(j - 1)），那么说明这时字符是重复的，直接等于上一个状态的结果再+1。
> 
> (3). 设立初始态：默认为0即可，本题通过条件自动更新。
> 
> 由于题目要求返回最大公共子串的长度，所以要设立一个变量max存储最大长度，更新max，最后返回max即可。

2. 普通思路

> 设置两层循环，外层循环控制子串的起始位置，内层循还向后遍历，新建一个StringBuilder的字符串sb（方便修改），内层循还向后遍历，将字符通过StringBuilder的append方法添加至sb，如果此时的字符串sb被字符串s2所包含，那么才能判断sb的长度（子串）是否大于保存的最大值max，遍历完所有子串的情况，最后返回即可。
> 
> 这里需要注意循环的条件和范围，范围都是对s1的限制。

3. 左右指针——可以看作普通思路的优化

> 设置左指针left从s1的左端开始，设置右指针right从s1的右端开始，思路有点像常规思路，外循环控制左指针的位置，内循环只要left <= right，就判断此时截取的s1.substring(left, right)是否被s2包含，并且长度有没有超过之前记录的最长子串的长度max，如果没有超过或者不符合条件，rright--，继续遍历；只要超过，就是这种情况（left = i）的最大长度（因为right一直在--），直接退出内循环（继续遍历也符合s2包含的条件，但长度越来越短，此时已经找到最长子串，没有必要继续）。
> 
> 由于题目要求返回最大公共子串的长度，所以要设立一个变量max存储最大长度，更新max，最后返回max即可。

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            String s1 = scanner.nextLine();
            String s2 = scanner.nextLine();
    
            System.out.println(comLen(s1, s2));
    
        }
    
        //1. 动态规划
        public static int comLen(String s1, String s2){
            int[][] res = new int[s1.length() + 1][s2.length() + 1];
            res[1][1] = 0;
            int max = 0;
            for (int i = 1; i <= s1.length() ; i++) {
                for (int j = 1; j <= s2.length(); j++) {
                    if(s1.charAt(i - 1) == s2.charAt(j - 1)){
                        res[i][j] = res[i - 1][j - 1] + 1;
                        if(max < res[i][j]){
                            max = res[i][j];
                        }
                    }
                }
            }
            return max;
        }
    
        //2. 普通思路
        public static int comLen1(String s1, String s2){
            int max = 0;
            for (int i = 0; i < s1.length(); i++) {
                StringBuilder sb = new StringBuilder();
                for(int j = i; j < s1.length(); j++){
                    if(s2.contains(sb.append(s1.charAt(j)))){
                        if(sb.length() > max){
                            max = sb.length();
                        }
                    }
                }
            }
            return max;
        }
    
        //3. 左右指针
        public static int comLen2(String s1, String s2){
            int max = 0;
            for (int i = 0; i < s1.length(); i++) {
                int left = i;
                int right = s1.length();
                while(left <= right){
                    int t = s1.substring(left, right).length();
                    if(s2.contains(s1.substring(left, right)) && max < t){
                        max = t;
                        break;
                    }
                    right--;
                }
            }
            return max;
        }
    }

如有建议或想法，欢迎一起讨论学习~

[n_3]: https://latex.csdn.net/eq?n%5E%7B3%7D