【Java版oj】day20字符串反转、公共子串计算

青旅半醒 2024-03-24 09:54 14阅读 0赞

**目录**

一、字符串反转

（1）原题再现

（2）问题分析

（3）完整代码

二、公共子串计算

（1）原题再现

（2）问题分析

（3）完整代码

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

> ## 一、字符串反转 ##
> 
> ### （1）原题再现 ###
> 
> [字符串反转\_牛客题霸\_牛客网][Link 1]
> 
> **描述**
> 
> 接受一个只包含小写字母的字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）
> 
> **输入描述：**
> 
> 输入一行，为一个只包含小写字母的字符串。
> 
> **输出描述：**
> 
> 输出该字符串反转后的字符串。
> 
> **示例1**
> 
> 输入：
> 
> abcd
> 
> 输出：
> 
> dcba
> 
> ### （2）问题分析 ###
> 
> 一般很容易想到，将字符串转成数组，然后对每个字符进行交换。固然不难，但是我们可以更简单，就是将String类转成StringBuilder类，然后使用直接使用StringBuilder中自带**reverse()反转函数**。
> 
> ### （3）完整代码 ###
> 
>     import java.util.*;
>     
>     /*
>      * 字符串反转
>      */
>     public class Main {
>         public static void main(String[] args) {
>             Scanner sc = new Scanner(System.in);
>             String str = sc.nextLine();
>             StringBuilder sb = new StringBuilder(str);
>             sb.reverse();
>             str = sb.toString();
>             System.out.println(str);
>         }
>     }
> 
> ![a897998bada0413bb261e997e1583f2a.png][]

> ## 二、公共子串计算 ##
> 
> ### （1）原题再现 ###
> 
> [公共子串计算\_\_牛客网][Link 2]
> 
> 给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。
> 
> 注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。
> 
> **输入描述:**
> 
> 输入两个只包含小写字母的字符串
> 
> **输出描述:**
> 
> 输出一个整数，代表最大公共子串的长度
> 
> **示例1**
> 
> 输入
> 
> asdfas
> 
> werasdfaswer
> 
> 输出
> 
> 6
> 
> ### （2）问题分析 ###
> 
> 这道题和day19号的第二道本质上是一样的，甚至比那道题更简单， 使用动态规划去做。
> 
>  **动态规划：**就和之前我讲解的那几篇解法一样。先找初始状态，再列出状态方程，最后返回目标位置。dp\[i\]\[j\]表示较短串在i位置，较长串在j位置时的子串长度。str1.charAt(i - 1) == str2.charAt(j - 1)如果该位置字符相等，则公共子串长度+1，在于最大公共子串长度比较，看是否要更新。 **注意：为什么是i-1和j-1，因为字符串下标是从0开始的，我定义的数组0行0列是初始值，第一个字符是从下标1开始的。**  
> 
> 
> ### （3）完整代码 ###
> 
>     import java.util.Scanner;
>     
>     /*
>      * 公共子串计算
>      */
>     public class Main {
>         public static void main(String[] args) {
>             Scanner sc = new Scanner(System.in);
>             String str1 = sc.nextLine();
>             String str2 = sc.nextLine();
>             int row = str1.length() + 1;
>             int col = str2.length() + 1;
>             int max = 0;
>             int [][]dp = new int [row][col];
>             for (int i = 1; i < row; i++) {
>                 for (int j = 1; j < col; j++) {
>                     if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
>                         dp[i][j] = dp[i - 1][j - 1] + 1;
>                     }
>                     max = Math.max(max, dp[i][j]);
>                 }
>             }
>             System.out.println(max);
>         }
>     }
> 
> ![a29c944adbe44e938735db0b7f5f3e43.png][]

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

![fdd5e101e1ee4bd29603a27510903b37.png][]

[Link 1]: https://www.nowcoder.com/practice/e45e078701ab4e4cb49393ae30f1bb04?tpId=37&tqId=21235&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37&difficulty=undefined&judgeStatus=undefined&tags=&title=
[a897998bada0413bb261e997e1583f2a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/3375893d51d943d8a0a668095b791166.png
[Link 2]: https://www.nowcoder.com/questionTerminal/98dc82c094e043ccb7e0570e5342dd1b?toCommentId=15606072
[a29c944adbe44e938735db0b7f5f3e43.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/7b445fcb4e184f98bcd944b0157df17d.png
[fdd5e101e1ee4bd29603a27510903b37.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/e3fdf574505749b4b0b71b932c7f941e.png