每日一刷《剑指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;
}
}