本文共 2981 字，大约阅读时间需要 9 分钟。

1.打印字符串的全部子序列

01 首先给定一个字符串，如何打印其全部的子序列

对其遍历，当前字符串一共两个选择，添加进去或者不添加进去。

// 找其全部子序列	public static void printAllSequences(String s) {
   		char[] chs = s.toCharArray();		String res = "";		process(chs,0,res);	}	public static void process(char[] chs,int i,String res) {
   		if(i==chs.length) {
   			System.out.println(res);			return;		}		process(chs, i+1, res+chs[i]);		process(chs, i+1, res);	}

结果为：

abc

ab

ac

a

bc

b

02 字符串的全排列问题

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

相比较上述的子序列而言，需要都遍历完所有的字符串

// 找其全排列	public static List
   
     res_all = new ArrayList<>();	public static String[] permutation(String s) {
   		char[] chs = s.toCharArray();		String res = "";		int i = 0;		process_2(chs,i,res);		return res_all.toArray(new String[res_all.size()]);	}	public static void process_2(char[] chs,int i,String res) {
   		// 截止条件		if(i==chs.length) {
   			res_all.add(res);			return;		}		// 避免重复		HashSet
    
      hashset = new HashSet
     
      ();		// 全排列		for(int j=i;j
     
    
   

03 回文子串问题

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：“abc”

输出：3

解释：三个回文子串: “a”, “b”, “c”

示例 2：

输入：“aaa”

输出：6

解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

解题思路来自中心点：

比如对一个字符串 ababa，选择最中间的 a 作为中心点，往两边扩散，第一次扩散发现 left 指向的是 b，right 指向的也是 b，所以是回文串，继续扩散，同理 ababa 也是回文串。

这个是确定了一个中心点后的寻找的路径，然后我们只要寻找到所有的中心点，问题就解决了。

中心点一共有多少个呢？看起来像是和字符串长度相等，但你会发现，如果是这样，上面的例子永远也搜不到 abab，想象一下单个字符的哪个中心点扩展可以得到这个子串？似乎不可能。所以中心点不能只有单个字符构成，还要包括两个字符，比如上面这个子串 abab，就可以有中心点 ba 扩展一次得到，所以最终的中心点由 2 * len - 1 个，分别是 len 个单字符和 len - 1 个双字符。

如果上面看不太懂的话，还可以看看下面几个问题：

• 为什么有 2 * len - 1 个中心点？
  aba 有5个中心点，分别是 a、b、c、ab、ba
  abba 有7个中心点，分别是 a、b、b、a、ab、bb、ba

• 什么是中心点？
  中心点即 left 指针和 right 指针初始化指向的地方，可能是一个也可能是两个

• 为什么不可能是三个或者更多？
  因为 3 个可以由 1 个扩展一次得到，4 个可以由两个扩展一次得到
  Java

// 中心点扩展		int res = 0;		// 中心点遍历		for(int counter=0;counter<2*s.length()-1;counter++) {
   			int left = counter/2;			int right = left + counter%2;						// 判断是否为回文串			while(left>=0&&right

04 最长回文子串问题

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

相比较上述，判断长度即可了。

class Solution {
       public String longestPalindrome(String s) {
           // 中心扩展		String res = "";				for(int counter=0;counter<2*s.length()-1;counter++) {
   			int left = counter / 2;			int right = left + counter % 2;			// 开始扩散			while(left>=0&&right
   
    res.length()) {
   					res = temp;				}								left--;				right++;			}		}		return res;    }}
   

05 最长回文子串

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。

注意:

假设字符串的长度不会超过 1010。

示例 1:

输入:

“abccccdd”

输出:

7

解释:

我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

该题不同于上面一题主要是该题是可以对字符串自由组合来得到最长，不是连续的，那么如何解题呢？

解题思路来自于对该字符串进行遍历，找到其字母的出现频率，其构成回文字符串的话是该频率为奇数个数有关的，若全为偶则整个长度，若有奇数则长度-奇数+1即可。

class Solution {
       public int longestPalindrome(String s) {
           int[] arr = new int[128];        for(char c:s.toCharArray()){
               arr[c]++;        }        int count = 0;        for(int i:arr){
               count += (i%2);        }        return count==0?s.length():(s.length()-count+1);    }}

转载地址：https://codingchaozhang.blog.csdn.net/article/details/110673872 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！