-2c57ec47146f40cbabf9adc9f224a0a3.jpg)
最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
- 题解
/**
* 无重复的最长子串
* 通过快慢下标。来模拟窗口，快下标往前走，往set中添加，并计算窗口的大小
* 当出现重复字符，则需要删除set中慢下标代表的元素，并移动慢下标
* @param s
* @return
*/
public int lengthOfLongestSubstring(String s) {
Set<Character> set=new HashSet<>();
int max=0,i=0,j=0;
while(i<s.length()&&j<s.length()){
//当set内部不存在当前字符时候。
if (!set.contains(s.charAt(i))){
//依此添加
set.add(s.charAt(i++));
//计算窗口的size；
max=Math.max(max,i-j);
}else {
//从慢下标删除
set.remove(s.charAt(j++));
}
}
return max;
}
回文字符串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false
题解：
/**
* 判断是否是回文字符串
* abcdcba noon
* @param s
* @return
* 题目已定这个空字符串属于回文串。所以不考虑了。
* 启用双指针大法，从前走和从后往回走。，只判断 数字字符和 大小写字母。
* 首先削减比较范围均是都变成小写。
* 然后判断。s[start]==s[end] 如果相等，那么就 start++ end--，比较下一个字符。
* 如果不等，从左走，或者从右走，都一样。只要遇到。s[start]==s[end] 不等的，直接返回，不符合回文字串。
*/
public boolean isPalindromeString(String s){
int left=0,right=s.length()-1;
s=s.toLowerCase();
while(left<right){
if (('0'<=s.charAt(left)&&s.charAt(left)<='9')||('a'<=s.charAt(left)&&s.charAt(left)<='z')){
if (('0'<=s.charAt(right)&&s.charAt(right)<='9')||('a'<=s.charAt(right)&&s.charAt(right)<='z')){
if (s.charAt(right)!=s.charAt(left)){
return false;
}else {
left++;
right--;
}
}else {
right--;
}
}else {
left++;
}
}
return true;
}
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: "aba"
输出: True
示例 2:
输入: "abca"
输出: True
解释: 你可以删除c字符。
/**
* 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
* @param s
* @return
* 同样也可以采用双指针来处理。根据题目的到只允许删除一个字符来判断是否是回文字符串，
* 那么当遇到s[start]==s[end] 不等的时候，删除左边往右走，或者删除右边往左走，需要记下左右删除的次数，
* 如果超过了1次，那么该字符串就不满足题意。
*/
public boolean validPalindrome(String s) {
int left=0,right=s.length()-1,leftDelete=-1,rightDelete=-1;
s=s.toLowerCase();
while(left<right){
if (('0'<=s.charAt(left)&&s.charAt(left)<='9')||('a'<=s.charAt(left)&&s.charAt(left)<='z')){
if (('0'<=s.charAt(right)&&s.charAt(right)<='9')||('a'<=s.charAt(right)&&s.charAt(right)<='z')){
if (s.charAt(right)!=s.charAt(left)){
if (leftDelete==-1){
//左边
leftDelete=left;
rightDelete=right;
left++;
}else if (rightDelete==s.length()){
return false;
}else {
//左边
left=leftDelete;
right=rightDelete;
right--;
rightDelete=s.length();
}
}else {
left++;
right--;
}
}else {
right--;
}
}else {
left++;
}
}
return true;
}
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
/**
* 输出一个字符串中的最大回文字串 动态规划，
* 观察上面的暴力破解，会发现循环中有多次无用的最大值计算。要计算所有长度的最大回文字串，那么按照如下规则来比较。
* 判断1本身，和本身比较 是回文
* 如果1->2是字串，只有2中情况，判断[1]和[2] 是否相等 要么是回文，要么不是
* 同理想知道1->3是否是回文字串，判断2字串是不是回文，并且 [1]和[3]是否相等 要么是回文，要么不是
* 同理想知道1->4是否是回文字串，判断2-3字串是不是回文，并且 [1]和[4]是否相等 要么是回文，要么不是
* 同理想知道1->5是否是回文字串，判断2-4字串是不是回文，并且 [1]和[5]是否相等 要么是回文，要么不是
* 同样递推
* 判断2本身，和本身比较 是回文
* 如果2->3是字串，只有2中情况，判断[2]和[3] 是否相等 要么是回文，要么不是
* 同理想知道2->4是否是回文字串，判断3字串是不是回文，并且 [2]和[4]是否相等 要么是回文，要么不是
* 同理想知道2->5是否是回文字串，判断2-4字串是不是回文，并且 [2]和[5]是否相等 要么是回文，要么不是
* 所以： 当回文串的长度大于2的时候得到公式
* P(i,j)=P(i+1,j-1)&&S[i]==s[j];
* 在长度为1的时候其本身和本身比。在长度为2的时候，判断左右是否相等
* @param s
* @return 返回回文串就是最大的回文串
*/
public String longestPalindromeDP(String s) {
boolean[][] p=new boolean[s.length()][s.length()];
String result="";
int max=0;
//用来计算所有长度的回文串
for (int i=1;i<=s.length();i++){
for (int start=0;start<s.length();start++){
//获取所求长度的下标；
int end=start+i-1;
if (end>=s.length()){
break;
}
// 代表从start->end的子串是否是回文串。
p[start][end]=s.charAt(start)==s.charAt(end)&&(i==1||i==2||p[start+1][end-1]);
//使用i>max 是为了排除空字符
if (p[start][end]&&i>max){
//满足该串是回文串，设置为返回结果
result=s.substring(start,end+1);
}
}
}
return result;
}