每日一刷《剑指offer》字符串篇之编辑距离
编辑距离
难度：较难
描述
给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。
你可以对字符串进行3种操作：
1.插入一个字符
2.删除一个字符
3.修改一个字符。
举例
解题思路
字符串比较
编辑距离是一类非常经典的动态规划的题目。 我们使用dp[i][j]表示字符串A的前i个字符与字符串B的前j个字符相同所需要的编辑距离。 首先需要进行状态的初始化，当一个字符串为空时，编辑距离等于另一个字符串的长度 对于状态转移方程，需要分两种情况讨论： 第一种情况，a[i]==b[j]，这种情况下，我们不需要进行编辑，dp[i][j]=dp[i-1][j-1] 第二种情况，a[i]!=b[j]，如果两个字符不相等，我们有三种处理方式：替换字符串b，编辑距离为dp[i-1][j-1]+1；插入一个字符与其相等，则编辑距离为dp[i-1][j]+1；删除该字符，编辑距离为dp[i][j-1]+1，三者取其小即可。 具体以下图为例
实现代码（java）
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param str1 string字符串 * @param str2 string字符串 * @return int整型 */ public int editDistance (String str1, String str2) { // write code here int[][] dp = new int[str1.length()+1][str2.length()+1]; //定义动规数组 for(int i=1; i<=str1.length(); i++){ // 初始化 dp[i][0] = i; } for(int i=1; i<=str2.length(); i++){ // 初始化 dp[0][i] = i; } for(int i=1; i<=str1.length(); i++){ for(int j=1; j<=str2.length(); j++){ if(str1.charAt(i-1)==str2.charAt(j-1)){ //第一种情况 dp[i][j] = dp[i-1][j-1]; }else{ //第二种情况 dp[i][j] = Math.min(dp[i-1][j]+1, Math.min(dp[i-1][j-1]+1, dp[i][j-1]+1)); //状态转移方程 } } } return dp[str1.length()][str2.length()]; } }
学习完本题的思路你可以解决如下题目：
最长的括号子串
难度：较难
描述
给出一个长度为 n 的，仅包含字符 '(' 和 ')' 的字符串，计算最长的格式正确的括号子串的长度。
例1: 对于字符串 "(()" 来说，最长的格式正确的子串是 "()" ，长度为 2 .
例2：对于字符串 ")()())" , 来说, 最长的格式正确的子串是 "()()" ，长度为 4 .
举例
解题思路
方法一：双指针；
- 新建两个变量left和right，分别记录左右括号出现次数。
- 正向遍历一次字符串，如果左右括号相等，则更新格式正确的括号子串长度，取较大者。如果左括号数小于右括号数，说明有不合法右括号（前面没有左括号与之匹配），重置为0。
- 最后反向遍历一次字符串，如果左右括号相等，则更新格式正确的括号子串长度，取较大者。如果左括号数大于右括号数，说明有不合法左括号（后面没有右括号与之匹配），重置为0。
方法二：栈； 因为括号需要一一匹配，而且先来的左括号，只能匹配后面的右括号，因此可以考虑使用栈的先进后出功能，使括号匹配。
具体做法：
- step 1：可以使用栈来记录左括号下标。
- step 2：遍历字符串，左括号入栈，每次遇到右括号则弹出左括号的下标。
- step 3：然后长度则更新为当前下标与栈顶下标的距离。
- step 4：遇到不符合的括号，可能会使栈为空，因此需要使用start记录上一次结束的位置，这样用当前下标减去start即可获取长度，即得到子串。
- step 5：循环中最后维护子串长度最大值。
实现代码（java）
方法一：
import java.util.*; public class Solution { /** * * @param s string字符串 * @return int整型 */ public int longestValidParentheses (String s) { // write code here int max=0; //分别记录左右括号出现次数 int left=0,right=0; //正向遍历 for(int i=0;i<s.length();i++){ if(s.charAt(i)=='('){ left++; } else{ right++; } //如果左右括号相等，则更新格式正确的括号子串长度，取较大者 if(left==right){ max=Math.max(max,right*2); } //如果左括号数小于右括号数，说明有不合法右括号，重置为0 else if(left<right){ left=right=0; } } left=right=0; //逆向遍历 for(int i=s.length()-1;i>=0;i--){ if(s.charAt(i)=='('){ left++; } else{ right++; } //如果左右括号相等，则更新格式正确的括号子串长度，取较大者 if(left==right){ max=Math.max(max,left*2); } //如果左括号数大于右括号数，说明有不合法左括号，重置为0 else if(left>right){ left=right=0; } } return max; } }
方法二：
import java.util.*; public class Solution { public int longestValidParentheses (String s) { int res = 0; //记录上一次连续括号结束的位置 int start = -1; Stack<Integer> st = new Stack<Integer>(); for(int i = 0; i < s.length(); i++){ //左括号入栈 if(s.charAt(i) == '(') st.push(i); //右括号 else{ //如果右括号时栈为空，不合法，设置为结束位置 if(st.isEmpty()) start = i; else{ //弹出左括号 st.pop(); //栈中还有左括号，说明右括号不够，减去栈顶位置就是长度 if(!st.empty()) res = Math.max(res, i - st.peek()); //栈中没有括号，说明左右括号行号，减去上一次结束的位置就是长度 else res = Math.max(res, i - start); } } } return res; } }
学习完本题的思路你可以解决如下题目： BM73.最长回文子串
最长回文子串
难度：中等
描述
对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。
举例
解题思路
方法一：中心扩散；
- 每个字符都可以尝试作为中心点看，会出现两种情况：可能是类似 aba 的字符串，也可能是类似 abba 的情况
- 只需要分别计算出以一个和两个字符作为中心点的子串，取出较大的长度即可
- 从left到right开始向两边扩散、比较，如果相等则继续扩散比较
- 如果不相等则剪枝，不用再继续扩散比较
- 计算每次比较的回文子串长度，取最大
方法二：动态规划；维护一个布尔型的二维数组dp，dp[i][j]表示 i 到 j 的子串是否是回文子串
每次先判断边界字符是否相等，再取决于上个状态的判断结果
算法流程：
- 维护一个布尔型的二维数组dp，
dp[i][j]表示 i 到 j 的子串是否是回文子串 - 从长度0到字符串长度n进行判断
- 选定起始下标 i 和终止下标 j， i 和 j 分别为要比较的字符串的左右边界指针
- 从左右边界字符开始判断，即 A.charAt(i) == A.charAt(j)
- 当相等时，还要判断当前长度 c 是否大于1，不大于则表明只有两个字符的字符串，一个或两个字符肯定是回文串，如“11”
- 判断的长度大于1时，因为最左右的字符已经相等，因此取决于上一次的子串是否是回文子串, 如 “12121”
- 更新回文串的最大长度
实现代码（java）
方法一：
import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { if(n < 2) { return n; } // 最大长度 int res = 0; // 每个字符都可以尝试作为中心点 for(int i = 0; i < n; i++) { // 两种情况：可能是类似 aba 的字符串，也可能是类似 abba 的情况 // 只需要分别计算出以一个和两个字符作为中心点的子串，取出较大的长度即可 int len = helper(A, i, i) > helper(A, i, i+1) ? helper(A, i, i) : helper(A, i, i + 1); // 更新最大长度 res = Math.max(res, len); } return res; } public int helper(String A, int left, int right) { // 从left到right开始向两边扩散、比较 while(left >= 0 && right < A.length()) { // 如果相等则继续扩散比较 if(A.charAt(left) == A.charAt(right)) { left--; right++; continue; } // 如果不相等则剪枝，不用再继续扩散比较 break; } // "+1"是因为通过下标计算子串长度 // "-2"是因为上边的while循环是当索引为left和right不想等才退出循环的 // 因此此时的left和right是不满足的，需要舍弃 return right - left + 1 - 2; } }
方法二：
import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { // 动态规划：i到j的子串是否是回文子串 boolean[][] dp = new boolean[n][n]; int max = 0; // 字符串长度差 c = j-i，即当前要比较的字符串长度，这里可以 c <= n / 2 + 1，减少判断次数 for(int c = 0; c <= n + 1; c++) { // 起始下标，范围取决于要判断的字符串长度c // i 和 j 分别为要比较的字符串的左右边界指针 for(int i = 0; i < n - c; i++) { // 终点下标 int j = c + i; // 左右边界的字符相等 if(A.charAt(i) == A.charAt(j)) { // c <= 1表示只有两个字符的字符串，一个或两个字符肯定是回文串 if(c <= 1) { dp[i][j] = true; } else { // 对于两个字符以上的字符串 // 因为最左右的字符已经相等，因此取决于内层的子串是否是回文子串 dp[i][j] = dp[i + 1][j - 1]; } // 更新回文串的最大长度，c代表判断的子串长度，越来越大 if(dp[i][j]) { max = c + 1; } } } } return max; } }
