字符串习题总结3
目录
一.去除重复字母
1.题目
2.图解说明
3.代码
二.把数字翻译成字符串
1.题目
2.思路图解
3.代码
三.正则表达式的匹配
1.题目
2.思路图解
3.代码
四.最长不含重复字符的子字符串
1.题目
2.思路图解
3.代码
五.最长回文子序列
1.题目
2.思路图解
3.代码
六.字符串中的变位词
1.题目
2.思路图解
3.代码
七.最小覆盖子串
1.题目
2.思路图解
3.代码
一.去除重复字母
1.题目
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例：
输入：s = "bcabc" 输出："abc"
2.图解说明
首先使用整型数组统计元素出现的次数，布尔类型数组用来记录当前元素是否被使用过，然后使用栈先进后出的规则来实现字典序最小。在进行比较的时候，如果栈顶元素比当前元素大，是否弹出还需要判断当前栈顶元素在之后是否还会出现，如果不会出现，就不能进行删除；否则就可以弹出栈，保持字典序最小。
3.代码
public String removeDuplicateLetters(String s) {
Deque<Character> stack = new ArrayDeque<>();
//记录每个字符出现的次数
int[] chars = new int[256];
//标记当前字符是否被使用过
boolean[] flag = new boolean[256];
for(char c:s.toCharArray()) {
chars[c]++;
}
for(char c:s.toCharArray()) {
//每处理一个字符，字符出现的次数减1
chars[c]--;
//说明当前字符已经使用过了，跳过
if(flag[c]) continue;
//当栈顶字符大于当前字符
while(!stack.isEmpty() && stack.peek()>c) {
//当栈顶字符在最后没有出现过，就不能弹出
if(chars[stack.peek()]==0) {
//说明后面不会出现
break;
}else {
//说明后面还会出现，弹出该元素，并设置该元素未访问
flag[stack.pop()] = false;
}
}
//将当前元素入栈
stack.push(c);
flag[c] = true;
}
//将栈中元素弹出并进行反转
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()) {
sb.append(stack.pop());
}
//反转结果并返回
return sb.reverse().toString();
}二.把数字翻译成字符串
1.题目
有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。
我们把一个字符串编码成一串数字，再考虑逆向编译成字符串。
由于没有分隔符，数字编码成字母可能有多种编译结果，例如 11 既可以看做是两个 'a' 也可以看做是一个 'k' 。但 10 只可能是 'j' ，因为 0 不能编译成任何结果。
现在给一串数字，返回有多少种可能的译码结果
2.思路图解
根据动态规划保存前面数字串可以组成字母不同的字母串次数，然后再计算当前位的字母串个数，当前位如果不为0，先将当前位置单独译码，结果为dp[i-1]；如果当前位置的字符可以和前一个字符组合满足10~26之间，说明可以和前一个字符组合进行译码，如果当前是第二个元素，就给前一个dp[i-1]+1，否则就是一个字符译码和两个字符译码的和（之前已经保存了一个字符译码），这里只要加上dp[i-2]即可。最终返回dp最后一个元素。
3.代码
public int solve (String nums) {
// write code here
int n = nums.length();
int[] dp = new int[n];
dp[0] = 1;
for(int i=1; i<n; i++) {
if(nums.charAt(i)!='0') {
dp[i] = dp[i-1];
}
//判断当前位和前一位是否可以合并
int num = (nums.charAt(i-1)-'0')*10+(nums.charAt(i)-'0');
if(num>=10 && num<=26) {
//说明可以和前一个合并
if(i==1) {
dp[i]+=1;
}else {
dp[i] += dp[i-2];
}
}
}
return dp[n-1];
}三.正则表达式的匹配
1.题目
请实现一个函数用来匹配包括'.'和'*'的正则表达式。
（1）模式中的字符'.'表示任意一个字符
（2）模式中的字符'*'表示它前面的字符可以出现任意次（包含0次）。
（3）str 只包含从 a-z 的小写字母。
（4）pattern 只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。
示例：匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
2.思路图解
使用二维dp数组的i表示str的第i-1个元素，用j表示pattern的第j-1个元素，dp[i][j]表示str的前i个元素和pattern的前j个元素是否匹配。
（1）首先考虑特殊情况，当两个串都为空时匹配成功，dp[0][0]=true;当pattern为空，str非空，表示匹配失败，dp[0][j]=false(其中j>0);当str为空，pattern非空，还需要进行匹配（为*时前面的字符可以为0个）。
（2）以当前元素是否为*进行分类，当前元素非*时，首先判断i-1和j-1位置的元素是否相等或j-1位置的元素为 . ，说明当前匹配成功，当前dp[i][j]的状态就为前一次dp[i-1][j-1]的状态；
当前元素为*时，先直接初始化当前*匹配的字符为0，为0时，相当于str的字符状态不变，修改pattern字符状态为*的前一位元素，及dp[i][j] =dp[i][j-2]；当满足*匹配一个或多个时的条件
（str[i-1]==pattern[j-2] || str[j-2]=='.'），就匹配str的前一个元素状态，dp[i][j] |= dp[i-1][j] （这里取|=是因为初识化dp[i][j] =dp[i][j-2]可能dp[i][j]已经匹配成功了）。
（3）返回最后dp最后一个元素。
3.代码
public boolean match (String str, String pattern) {
// write code here
int m = str.length(), n = pattern.length();
boolean[][] dp = new boolean[m+1][n+1];
//这里str为空，pattern不为空默认都为false，不匹配；
for(int i=0; i<=m; i++) {
for(int j=0; j<=n; j++) {
//处理模式串为空串
if(j==0){
//其中包含str空和非空
dp[i][j] =(i==0);
}else {
//处理pattern非*
if(i>0 && (str.charAt(i-1)==pattern.charAt(j-1) || pattern.charAt(j-1)=='.')) {
dp[i][j] = dp[i-1][j-1];
}else {
//处理pattern为*
if(j>=2) dp[i][j] |= dp[i][j-2];//默认处理*匹配为0
//满足匹配一个或多个条件就处理多个
if(i>=1 && j>=2 && (str.charAt(i-1)==pattern.charAt(j-2) || pattern.charAt(j-2)=='.')) {
dp[i][j] |= dp[i-1][j];//匹配str的前一个
}
}
}
}
}
return dp[m][n];
}四.最长不含重复字符的子字符串
1.题目
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例：
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
2.思路图解
因为从头开始向后寻找无重复字符的字符串时，假如第一个无重复字符的子字符串的左边界为i，右边界为j;而寻找下一个子字符串时是从i+1位置开始，这里从i+1~j位置没有重复的字符，所以利用这个特点我们可以用滑动窗口来解决问题，这里我们通过Set来判断当前子字符串是否有重复的字符，遇到第一个字符，直接加入到set中，然后向后寻找，之后如果没有遇到重复的就一直加入到set中，然后扩大右窗口，直到遇到重复的，退出循环，然后开始记录最大的长度，下一次需要缩小左窗口，并从set中删除该元素，直到遍历结束。
3.代码
public int lengthOfLongestSubstring(String s) {
int res = 0;
int end = -1;//滑动窗口的右边界
Set<Character> set = new HashSet<>();
for(int i=0; i<s.length(); i++) {
if(i!=0) set.remove(s.charAt(i-1));//去除左边界的元素
//在没有重复的情况下扩大右边界
while(end+1<s.length() && !set.contains(s.charAt(end+1))) {
set.add(s.charAt(end+1));
end++;
}
//保存最大值
res = Math.max(res, end-i+1);
}
return res;
}五.最长回文子序列
1.题目
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例：
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。
2.思路图解
利用动态规划，使用二维dp数组，其中dp[i][j]表示从i~j的子串最长回文长度，由于每次给在区间为i+1~j-1的子回文串添加左右字符，然后再求新的最长回文串，如果i和j位置的元素相等，那么从i-j的子字符串也为回文串，及dp[i][j]=dp[i+1][j-1]+2，否则就保存从i-j-1，或从i+1,j的回文子串的最大值。（在求解的过程中遇到i,j相等的位置直接初始化为1）
3.代码
public int longestPalindromeSubseq(String s) {
int n = s.length();
//dp中的i，j表示从i~j之间的子字符串的最长回文结构
int[][] dp = new int[n][n];
for(int i=n-1;i>=0;i--) {
char c1 = s.charAt(i);
//对于相等的元素默认为1
dp[i][i] = 1;
//判断给i+1~j-1之间的回文序列两边加上两个相等或不等的最长回文
for(int j=i+1; j<n; j++) {
char c2 = s.charAt(j);
if(c1==c2) {
dp[i][j] = dp[i+1][j-1]+2;
}else {
//新添加的左右不能构成新的回文，保存之前最长的回文结构
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][n-1];
}六.字符串中的变位词
1.题目
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
示例：
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
2.思路图解
首先使用两个数组用来记录s1和s2字符出现的次数，题目是判断s2中和s1长度相同的子串是否和s1的字符全部相同；这里使用count1来记录s1所有元素出现的次数，然后count2来记录和s1长度相等的字符串作为初始滑动窗口，之后每次变化窗口大小后比较count1和count2数组是否相等,如果相等就说明存在变位词。这里窗口的变换规则为去除窗口头的元素，添加新元素到窗口尾。
3.代码
public boolean checkInclusion(String s1, String s2) {
int l1 = s1.length(), l2 = s2.length();
if(l1>l2) return false;
int[] cnt1 = new int[26];
int[] cnt2 = new int[26];
//统计s1中每个字符出现的次数
for(int i=0; i<l1; i++) {
cnt1[s1.charAt(i)-'a']++;
//初始化滑动窗口大小
cnt2[s2.charAt(i)-'a']++;
}
//比较滑动窗口中字符出现次数是否相等
if(Arrays.equals(cnt1, cnt2)) return true;
//然后修改滑动窗口大小
for(int i=l1; i<l2; i++) {
cnt2[s2.charAt(i)-'a']++;
cnt2[s2.charAt(i-l1)-'a']--;
if(Arrays.equals(cnt1, cnt2)) return true;
}
return false;
}七.最小覆盖子串
1.题目
给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。
数据范围：0≤∣S∣,∣T∣≤100000 \le |S|,|T| \le100000≤∣S∣,∣T∣≤10000，保证s和t字符串中仅包含大小写英文字母
例如：
S="XDOYEZODEYXNZ" T="XYZ"
找出的最短子串为"YXNZ"
2.思路图解
借助滑动窗口的思想，首先使用一个数组来记录元素出现的次数，首先遍历T中所有字符，遇到就给指定位置结果减一，结束后再遍历S，遍历过程中如果遇到数组中所有位置元素都大于0，说明找到了一个覆盖子串，接下来从头缩小窗口大小，满足数组所有元素都大于0（说明还是子串），这时候再记录最短子串的起点和终点，最终遍历结束即可。
然后判断left是否为-1,如果为-1说明没有找到覆盖子串，直接返回空串；否则截取覆盖子串。
3.代码
public String minWindow (String S, String T) {
// write code here
int left=-1, right = -1;
int beign=0, end=0;
//保留滑动窗口的大小
int mWin = S.length()+1;
int[] hash = new int[128];
for(char c:T.toCharArray()) hash[c]--;
while(end<S.length()) {
//取一个元素就加1
hash[S.charAt(end)]++;
//每次缩小一个就验证依次是否满足覆盖串
while(isCheck(hash)){
//判断是否有必要缩小
if(mWin>=end-beign+1) {
left = beign;
right = end;
mWin = right-left+1;
}
//每缩小一个就修改hahs对应元素
hash[S.charAt(beign)]--;
beign++;
}
end++;
}
if(left==-1) return "";
return S.substring(left, right+1);
}
public boolean isCheck(int[] hash) {
for(int i=0; i<hash.length; i++) {
if(hash[i]<0) return false;
}
return true;
}