一、字符串反转 （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); } }
二、公共子串计算 （1）原题再现 给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。 注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。 输入描述: 输入两个只包含小写字母的字符串 输出描述: 输出一个整数，代表最大公共子串的长度 示例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); } }
