字符串习题总结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 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
            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 set = new HashSet<>();
        for(int i=0; i
            if(i!=0) set.remove(s.charAt(i-1));//去除左边界的元素
            //在没有重复的情况下扩大右边界
            while(end+11))) {
                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
                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
            cnt1[s1.charAt(i)-'a']++;
            //初始化滑动窗口大小
            cnt2[s2.charAt(i)-'a']++;
        }
        //比较滑动窗口中字符出现次数是否相等
        if(Arrays.equals(cnt1, cnt2)) return true;
        //然后修改滑动窗口大小
        for(int i=l1; 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
            //取一个元素就加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
            if(hash[i]<0) return false;
        }
        return true;
    }