子串问题题解汇总 ---通俗易懂版
找到字符串的最长无重复字符子串
https://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4?tpId=190&&tqId=35220&rp=1&ru=/ta/job-code-high-rd&qru=/ta/job-code-high-rd/question-ranking
本文参考了几篇题解区大佬的文章，对以下做过的子串问题进行解析和总结。
找到字符串的最长无重复字符子串
方法一 滑动窗口法：
- 我们可以使用双指针模拟一个滑动窗口。
- 初始化窗口为 (left, right]。 所以left从-1开始。
- 窗口不断往右扩大。
- 根据题目的要求，即遇到有重复数字的，在窗口左侧缩小。
- 在每次滑动时，对窗口的大小进行比较，保留最大的长度。
代码实现：
public int maxLength (int[] arr) {
int res = 0, left = -1;
//用来存放窗口存放过的数字
HashMap<Integer, Integer> windows = new HashMap<>();
//窗口不断往右移
for(int right = 0; right < arr.length; right++){
//根据题目，当遇到重复的数字时，缩小左侧窗口
if( windows.containsKey(arr[right])){
//因为我们有可能遇到索引比left原来还小的相同数字
//所以这里要进行比较，目的还是为了缩小左侧窗口，确保窗口内全是不重复的数字
left = Math.max(left, windows.get(arr[right]));
}
//更新窗口内数字的索引
windows.put(arr[right], right);
//right-left是窗口大小
//因为要找最长，所以要进行比较
res = Math.max(res, right-left);
}
return res;
}方法二 **双指针+回头遍历**：
过程可以看注释
public int maxLength (int[] arr) {
int res = 0, tmp = 0;
//right指针往右移动
for(int right = 0; right < arr.length; right++){
int left = right - 1;
//回头扫描，要是没有找到相同的，左指针一直倒退
while(left >= 0 && arr[right] != arr[left])
left--;
//暂时保存子串长度
//若指针距离比上一个字符时拥有的子串长度大，就tmp + 1，否则就设置为指针距离，方便下一步res进行比较
tmp = tmp < right - left ? tmp + 1 : right - left;
res = Math.max(res,tmp);
}
return res;
最长公共子串
这道题有点类似 最长公共子序列。
公共子串和公共子序列的区别
- 公共子串：必须是连续的。
- 公共子序列：不必是连续的，但是相对位置必须不能改变。
好，接下来，我们上动态规划解法：
- 其实解法跟最长公共子序列的是差不多的。
- 先确定状态和选择
- 状态有两个，分别是str1 和 str2 的索引 i,j 变化
- 选择有两个，当str1[i-1] 和 str2[j-1]相等时，dp[i][j] + 1；当不相等时，dp[i][j]置为0。
- 确定状态转移方程和 base case
- 这里画个图就清晰多了
当字符相等时，dp[i][j] = dp[i-1][j-1] + 1；
不相等时，dp[i][j] = 0 - base case：dp[0][j] 和 dp[i][0] 全部置为0。
- 这里画个图就清晰多了
代码实现：
public String LCS(String str1, String str2){
if(str1.length() == 0 || str2.length() == 0){
return "-1";
}
//起始位置
int start1 = 0;
//偏移量
int max = 0;
int len1 = str1.length();
int len2 = str2.length();
int[][] dp = new int[len1+1][len2+1];
for(int i = 1; i <= len1; i++){
for(int j = 1; j <= len2; j++){
if(str1.charAt(i-1) == str2.charAt(j-1)){
//将当前相等的字符计入 + 1
dp[i][j] = dp[i-1][j-1] + 1;
}else {
dp[i][j] = 0;
}
if(max < dp[i][j]){
//max记录已经拥有的子串长度
max = dp[i][j];
//因为字符串索引是从0开始的，所以 i - max 刚好是起始位置
start1 = i - max;
}
}
}
if(max == 0) return "-1";
return str1.substring(start1, max+start1);
}最长回文子串
代码实现：
public class Palindrome {
public int getLongestPalindrome(String A, int n) {
int res = 0;
//暴力解法
for(int i = 0; i < n; i++){
for(int j = i+1; j <= n; j++){
String tmp = A.substring(i,j);
//调用判断是否为回文子串的方法
if(isPalindrome(tmp)){
res = Math.max(res, tmp.length());
}
}
}
return res;
}
public boolean isPalindrome(String s) {
int len = s.length();
for(int i=0; i< len/2; i++){
if(s.charAt(i) != s.charAt(len-1-i))
return false;
}
return true;
}
}
回文问题
寻找最长回文子串，不是求长度
其实大同小异，也是同样使用双指针法
public class Palindrome{
String res;
public String longest(String s){
res = new String();
for(int i = 0; i < s.length(); i++){
//寻找长度为基数的回文子串
String s1 = String palindrome(s, i, i);
//寻找长度为偶数的回文子串
String s2 = String palindrome(s, i, i+1);
res = res.length() > res : s1;
res = res.length() > res : s2;
}
return res;
}
public String palindrome(String s, int l, int r){
while( l >= 0 && r < s.length(); && s.charAt(l) == s.charAt(r)){
l--; r++;
}
return s.subString(l, r+1);
}
}最长回文串 不是子串
class Solution {
public int longestPalindrome(String s) {
//因为在ASCII码中，A到z是65到122 总共58个
int[] cnt = new int[58];
for(char c : s.toCharArray()){
cnt[c - 'A'] += 1;
}
int ans = 0;
for(int x : cnt){
//如果是偶数 就ans+x; 如果是奇数 就减掉一个再ans+x
ans += x - (x & 1);
}
//回文串要么全是偶数个数 要么除了偶数个数外，只有一个奇数
return ans < s.length() ? ans + 1 : ans;
}
}最长的括号子串
绝了这道题，一开始写了个使用栈的解法，测试一直过不了。后来看了题解，才发现自己理解错题目了呜呜呜。 上正确解法：
方法一 使用栈 ：
这个应该是很容易想到的解法
- 栈存放的是括号的索引。
- 当遇到 '('时，入栈，当遇到 ')'时，如果栈为空，将它放进去；否则弹出栈顶，再将当前索引减去栈顶的索引，再跟原来的res进行比较，更新res值，保证取到最大的数字。
代码实现：
public int longestValidParentheses (String s) {
int res = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for(int i=0; i < s.length(); i++){
if(s.charAt(i) == '('){
stack.push(i);
} else {
stack.pop();
if(stack.empty()) {
stack.push(i);
} else {
res = Math.max(res, i - stack.peek());
}
}
}
return res;
}方法二 动态规划：
dp数组存放的是当前所拥有的括号子串长度。
在动态规划框架上，处理了三种情况：
- 当前字符为 '('，跳过，默认初始化为0;
- 当前字符为 ')'，又分为两种情况：
- 当前面只有单个'()'出现或者判断字符正处于嵌套括号的最里层时，dp[i] = dp[i-2] + 2；
- 当处于嵌套括号的外层时， dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2；
代码实现：
public int longestValidParentheses (String s) {
int res = 0;
int[] dp = new int[s.length()];
for(int i = 1; i < s.length(); i++){
//只对当前字符是')'进行处理
if(s.charAt(i) == ')'){
//当()时
if(s.charAt(i-1) == '('){
dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
} else if(i - dp[i-1] > 0 && s.charAt(i - dp[i-1] - 1) == '('){ //当 (())时
dp[i] = dp[i-1] + ((i-dp[i-1]) >= 2 ? dp[i - dp[i-1] - 2] : 0) + 2;
}
res = Math.max(res, dp[i]);
}
}
return res;
}最长的覆盖子串
这道题也可以用滑动窗口方法：
与第一题不同的是，窗口左侧收缩的满足条件是 当S包含T的所有字符时。
代码实现：
public String minWindow (String S, String T) {
// write code here
HashMap<Character, Integer> need, window;
need = new HashMap<Character, Integer>();
window = new HashMap<Character, Integer>();
for(int i=0; i < T.length(); i++){
char c = T.charAt(i);
need.put(c,need.getOrDefault(c,0)+1);
}
int left = 0, right = 0;
//包含目标T的字符数
int valid = 0;
//记录最小覆盖子串的起始索引及长度
int start = 0, len = Integer.MAX_VALUE;
//窗口不断往右移
while(right < S.length()){
char c = S.charAt(right);
//右移窗口
right++;
//进行窗口内数据更新
if(need.containsKey(c)){
window.put(c,window.getOrDefault(c,0)+1);
if(window.get(c) == need.get(c))
valid++;
}
//判断左侧是否进行收缩
while(valid == need.size()){
//更新最小覆盖子串
if(right - left < len){
start = left;
len = right - left;
}
char d = S.charAt(left);
//左移窗口
left++;
//进行窗口内数据更新
if(need.containsKey(d)) {
if(window.get(d) == need.get(d))
valid--;
window.put(d,window.get(d)-1);
}
}
}
return len == Integer.MAX_VALUE ? "" : S.substring(start,start+len);
}