目录
一.最长回文子串
?1.题目
给你一个字符串?s，找到?s?中最长的回文子串。
示例：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
2.图解
3.代码
public String longestPalindrome(String s) {
//设置两个指针保存回文串的开始和结束位置
int begin = 0;
int end = 0;
for(int i=0; i<s.length(); i++) {
//字符串长度有奇偶，所以需要求奇偶中的最大值
int len1 = huiWenLen(s, i, i);
int len2 = huiWenLen(s, i, i+1);
int len = Math.max(len1, len2);
if(len>end-begin) {
//当为偶数的时候，如abb（结果为bb）这时候就会多算如果begin=i-len/2就会减一个，导致错误
begin = i-(len-1)/2;
end = i+len/2;
}
}
//字符串截取的是从begin开始，到end+1结束（不包含end+1）
return s.substring(begin, end+1);
}
//从当前元素开始向两边开始查找是否为回文串
public int huiWenLen(String str, int left, int right) {
int l = left, r = right;
while(l>=0 && r<str.length() && str.charAt(l)==str.charAt(r)) {
l--;
r++;
}
return r-l-1;
}二.求数组所有集合的全排列（和求字符串的所有子串方法相同）
1.题目
现在有一个没有重复元素的整数集合S，求S的所有子集
注意：
你给出的子集中的元素必须按升序排列
给出的解集中不能出现重复的元素
示例：
输入：[1,2,3]
返回值：[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
2.图解
3.代码
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(S==null || S.length==0) {
return res;
}
for(int i=0; i<=S.length; i++) {
//控制长度，调用递归函数依次查找
dfsColl(S, 0, i, res, new ArrayList<>());
}
return res;
}
public void dfsColl(int[] arr, int begin,int len , ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list) {
//满足指定长度，就添加到结果集中
if(len == list.size()) {
res.add(new ArrayList<>(list));
}
//从开始位置一直向后寻找
for(int i=begin; i<arr.length; i++) {
//将当前元素添加到list中
list.add(arr[i]);
//然后递归再向后查找
dfsColl(arr, i+1, len, res, list);
//当前元素的指定长度查找完后，删除当前元素
list.remove(list.size()-1);
}
}三.求一个字符串的所有回文子串（中心扩展法）
1.题目
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindromic-substrings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例：s="aaba"
输出res=?6 ，其中回文串有a ,a ,b ,a ,aa ,aba
2.思路图解
（1）方法1
首先一个字符肯定是回文的，当以该字符为中心时，继续分别以left和right向两边扩展并验证为子串时，这时候就是一种思路，但是存在一种情况，那就是相同的两个字符也可以组成作为一个中心向外扩散，例如aa,这时候我们就要根据奇偶来进行区分（可能会有一个疑问，那也可能会有3个或4个作为回文中心；因为3个就是1个的扩展，4个就是2个的扩展，所以我们就只根据奇偶讨论2个和1个）；使用2个字符作为中心进行扩展时，需要判断这2个字符相等才能接着进行扩展。
?（2）方法2
思路和方法1相同，只不过在对于根据奇偶个数进行扩展的时候合并到了一起，减小了代码量。
首先通过上面处理的结果可以看出，总共有s.length*2-1个中心需要进行扩展；然后再找关系，然后可以总结出，从【0，s.length*2-1】之间，所有的左边界left=i/2；所有的右边界right=left+i%2;
之后还是通过中心扩展的方法进行求解（在扩展的过程中也判断了为偶数的2个字符作为中心是否相等）。
3.代码
（1）方法1
public int countSubstrings(String s) {
//这里自身就是回文，所以先统计自身
int res = s.length();
//以奇数进行扩展
for(int i=0; i<s.length(); i++) {
int left = i-1;
int right = i+1;
while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)) {
res++;
left--;
right++;
}
}
//以偶数进行扩展
for(int i=0; i<s.length()-1; i++) {
//说明2个字符可以作为扩展中心
if(s.charAt(i)==s.charAt(i+1)) {
res++;
int left = i-1;
int right = i+2;
while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)) {
res++;
left--;
right++;
}
}
}
return res;
}（2）方法2?
public int countSubstrings(String s) {
int res = 0;
//总共需要匹配len*2-1次，之后会根据奇偶向两边扩展，如果是回文
//res++,否则就判断下一个（判断过程中注意边界问题）
for(int i=0; i<s.length()*2-1; i++) {
int left = i/2;
int right = left+i%2;
while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)) {
res++;
left--;
right++;
}
}
return res;
}四.求二进制和
1.题目
给定两个用字符串表示的二进制数，返回他们的和。
数据范围：字符串长度满足?1\le n \le 10^5 \1≤n≤105??，字符串中只含有 0 和 1，且保证除 0 以外的二进制数没有前导零的情况。
示例：
输入："101","1"
返回值："110"
2.思路图解
思路：
思路：
首先需要一个保存需要进位的数命名为carry（初始值为0），
然后计算当前位置的和(包含进位的值), sum=A.charAt(i)+B.charAt(i)，
求当前位置和的时候还需要每次判断是否超过了源字符串的长度，如果超出，当前结果位置就为0
下一步是保存进位的值，为了下一位求和使用
再保存当前位置的和
图解：
3.代码
public String binaryAdd (String A, String B) {
// write code here
int aL = A.length()-1;
int bL = B.length()-1;
//表示进位
int carry = 0;
StringBuilder sb = new StringBuilder();
while(aL>=0 || bL>=0 || carry>0) {
//获取每个字符串的当前结果
int a = (aL<0?'0':A.charAt(aL--))-'0';
int b = (bL<0?'0':B.charAt(bL--))-'0';
//求总和（包含低位的进位和高位的和）
int sum = a+b+carry;
//保存进位结果
carry = sum/2;
//保存进位之后的当前位置的结果
sb.append(sum%2);
}
//最后将拼接好的结果进行反转
return sb.reverse().toString();
}五.分割回文串（分割后的字符串全为回文）
1.题目
给你一个字符串?s，请你将?s?分割成一些子串，使每个子串都是?回文串?。返回?s?所有可能的分割方案。
示例：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
2.思路图解
3.代码
List<List<String>> res = new ArrayList<>();
public List<List<String>> partition(String s) {
char[] charArray = s.toCharArray();
dfs(charArray, 0, s.length(), new ArrayList<>());
return res;
}
//求所有回文子串
public void dfs(char[] charArray, int index, int len, ArrayList<String> list) {
//说明字符串已经处理完成
if(index == len) {
res.add(new ArrayList<>(list));
return;
}
//依次取一部分，先判断是否为回文，是回文就向下处理，如果不是回文，跳过当前循环
for(int i=index; i<len; i++){
if(!isPartion(charArray, index, i)) {
continue;
}
list.add(new String(charArray, index, i-index+1));
dfs(charArray, i+1, len, list);
//处理完当前层的子字符串，删除掉，再处理当前层的后面子字符串
list.remove(list.size()-1);
}
}
//判断是否为回文串
public boolean isPartion(char[] charArray, int left, int right) {
while(left < right) {
if(charArray[left++] != charArray[right--]) {
return false;
}
}
return true;
}?
六.复原IP地址
1.题目
有效 IP 地址?正好由四个整数（每个整数位于?0?到?255?之间组成，且不能含有前导?0），整数之间用?'.'?分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入?'.' 来形成。你 不能?重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2.思路图解
3.代码
List<String> res = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
int len = s.length();
dfs(s, 0, 0, len, new ArrayList<String>());
return res;
}
//进行深度搜索进行处理
public void dfs(String s, int beign, int count, int len, ArrayList<String> list) {
//处理到了结尾，就直接保存并返回
if(beign == len) {
if(count==4)
res.add(String.join(".", list));
return;
}
//剪枝（字符长度小于之后截取的个数，字符长度大于截取个数的3倍）
if(len-beign<(4-count) || len-beign>3*(4-count)) {
return;
}
//处理当前的3个字符（1,2,3个分别连起来）
for(int i=0; i<3; i++) {
if(i+beign>=len) {
break;
}
int tmp = segment(s, beign,beign+i+1);
if(tmp != -1){
list.add(""+tmp);
dfs(s, beign+i+1, count+1, len, list);
//回溯
list.remove(list.size()-1);
}
}
}
//判断截取的字符串是否符合ip地址的规范，符合就转化为数字
public int segment(String s, int left, int right) {
//当第一长度大于1且第一位是0时就直接返回
if(right-left>1 && s.charAt(left)=='0') {
return -1;
}
//求字符串的10进制结果
int res = 0;
for(int i=left; i<right; i++) {
res = res*10+s.charAt(i)-'0';
}
//说明超过ip长度
if(res>255) {
return -1;
}
return res;
}七.最小覆盖子串
1.题目
给你一个字符串?s?、一个字符串?t?。返回?s?中涵盖?t?所有字符的最小子串。如果?s?中不存在涵盖?t?所有字符的子串，则返回空字符串?""?。
示例：
2.思路图解
求解思路就是使用两个hash表来存储字符串s和t中字符出现的次数，先统计字符串t，之后再通过滑动窗口的思想来将s中的字符添加到hash中，相当于是扩大窗口，在统计过程中如果窗口左边的元素没有在t中包含或者包含但重复较多，这时候就需要减小窗口的大小，这些操作都是基于hash表来操作。中间还需要一个count标记窗口中的元素是否已经包含了t中的所有字符，还需要一个len来标识是否是最小的覆盖子串。
3.代码
public String minWindow(String s, String t) {
HashMap<Character,Integer> ms = new HashMap<>();
HashMap<Character,Integer> mt = new HashMap<>();
//先统计t中字符出现的次数
for(int i=0; i<t.length(); i++) {
mt.put(t.charAt(i), mt.getOrDefault(t.charAt(i), 0)+1);
}
//保存结果值
String res="";
//记录当前长度，之后根据该长度要进行缩短字符串
int len = Integer.MAX_VALUE;
//left 和 right 表示滑动窗口的左右边界;count记录t在s中已经存在的个数
for(int left=0,right=0,count=0; right<s.length(); right++) {
//先将元素放到ms中
ms.put(s.charAt(right), ms.getOrDefault(s.charAt(right), 0)+1);
//判断该字符是否也出现在t中
if(mt.containsKey(s.charAt(right))) {
//还需要判断当前字符是否是t必须的（避免多个重复没用的字符）
if(ms.get(s.charAt(right))<=mt.get(s.charAt(right))) {
count++;
}
}
//如果s的left位置的元素不包含在t中 或 字符个数多余指定个数，那么就将该字符删除
while(left<right && (!mt.containsKey(s.charAt(left)) ||
ms.get(s.charAt(left))>mt.get(s.charAt(left)))) {
ms.put(s.charAt(left), ms.get(s.charAt(left))-1);
left++;
}
//满足count长度 然后 （根据len）判断是否需要缩短区间，若缩短，修改res
if(count==t.length() && right-left+1<len) {
len = right-left+1;
res = s.substring(left, right+1);
}
}
return res;
}八.电话号码的字母组合
1.题目
给定一个仅包含数字?2-9?的字符串，返回所有它能表示的字母组合。答案可以按?任意顺序?返回。
?示例：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
2.图解思路
通过递归回溯去处理每一个数字对应的字符，当递归处理到数字串的末端时，就保存结果，结束递归。
?
3.代码
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if(digits.length()==0) {
return res;
}
Map<Character, String> map = new HashMap<>();
map.put('2', "abc");
map.put('3', "def");
map.put('4', "ghi");
map.put('5', "jkl");
map.put('6', "mno");
map.put('7', "pqrs");
map.put('8', "tuv");
map.put('9', "wxyz");
dfs(0, digits, new StringBuilder(), map, res);
return res;
}
public void dfs(int index, String digits, StringBuilder sb, Map<Character, String> map, List<String> res) {
if(index==digits.length()) {
//说明数字已经处理到尾部
res.add(new String(sb));
return;
}
//没有处理完，就处理当前位置的数字(获取当前数字所对应的所有字符)
String str = map.get(digits.charAt(index));
//循环遍历当前字符并递归处理下一个数字
for(int i=0; i<str.length(); i++) {
sb.append(str.charAt(i));
//递归
dfs(index+1, digits, sb, map, res);
//回溯
sb.deleteCharAt(sb.length()-1);
}
}