字符串——算法专项刷题（三）

朴灿烈づ我的快乐病毒、 2024-04-01 16:58 43阅读 0赞

### 三、字符串 ###

字符串题目常用算法及思想： 滑动窗口、数组统计字母个数

注意点：字符串边界、窗口的维持

#### 3.1字符串中得变位词 ####

[原题链接][Link 1]

给定两个字符串 `s1` 和 `s2`，写一个函数来判断 `s2` 是否包含 `s1` 的某个变位词。

换句话说，第一个字符串的排列之一是第二个字符串的 **子串** 。

**示例 1：**

*  输入: `s1 = "ab" s2 = "eidbaooo"`
 *  输出: True
 *  解释: s2 包含 s1 的排列之一 (“ba”).

**提示：**

*  `1 <= s1.length, s2.length <= 104`
 *  `s1` 和 `s2` 仅包含小写字母

**思路：** 只要保证长度相等，出现的字符及个数相同，就符合条件。因为只包含26个小写字母，因此使用长度为26的数组记录出现的字符及个数，使用窗口保证长度相等，每遍历一个元素，移动窗口更新字符个数

**注意点：** 先统计s1字符串长度的字符，然后从这个长度开始遍历

class Solution {
        
        public boolean checkInclusion(String s1, String s2) {
        
            //记录 字母出现的次数
            int[] cnt1 = new int[26];
            int[] cnt2 = new int[26];
            int n = s1.length();
            int m = s2.length();
            if (n > m) return false;
    
            for (int i = 0; i < n; i++) {
        
                ++cnt1[s1.charAt(i) - 'a'];
                ++cnt2[s2.charAt(i) - 'a'];
            }
            
            if(Arrays.equals(cnt1,cnt2)) return true;
    
            for (int i = n; i < m; i++) {
        
                // 保证长度相等，每遍历一个字符左边 -1 右边+1  
          
                ++cnt2[s2.charAt(i) - 'a'];
                --cnt2[s2.charAt(i-n) - 'a'];
                //比较数组是否相等
                if(Arrays.equals(cnt1,cnt2)) return true;
    
            }
            return false;
    
    
        }
    }

#### 3.2字符串中的所有变位词 ####

[原题链接][Link 2]

给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

变位词 指字母相同，但排列不同的字符串。

**示例 1：**

*  输入: s = “cbaebabacd”, p = “abc”
 *  输出: \[0,6\]

**解释:**

*  起始索引等于 0 的子串是 “cba”, 它是 “abc” 的变位词。
 *  起始索引等于 6 的子串是 “bac”, 它是 “abc” 的变位词。

**提示:**

*  `1 <= s.length, p.length <= 3 * 104`
 *  `s` 和 `p` 仅包含小写字母

**思路：** 变位词 就是字符相同个数相等的两个字符串，与上一题思路相同，由于字符串s和p都仅包含小写字母，因此使用长度为26的数组记录字符出现的个数，然后通过比较数组是否各元素相等来判断是否符合条件

**注意点：** 先分别统计字符串p长度个字符，然后进行遍历，保证两个数组中记录的数据所对应的字符串的长度相等

class Solution {
        
        public List<Integer> findAnagrams(String s, String p) {
        
    
         List<Integer> list = new ArrayList();
          int len1 = s.length();
          int len2 = p.length();
      // 特判 
          if(len2 > len1)  return list;
    
          int[] num1 = new int[26];
          int[] num2 = new int[26];
    
          for(int i = 0; i < len2;i++){
        
               num1[p.charAt(i) - 'a']++;
               num2[s.charAt(i) - 'a']++;
           }
            
            //通过Arrays中的equals方法来比较两个数组中的数据是否相等
           if(Arrays.equals(num1,num2)){
        
               list.add(0);
           }
    
        for(int i = len2; i < len1 ;i++){
        
              num2[s.charAt(i) - 'a']++;
              num2[s.charAt(i - len2) - 'a']--;
    
              if(Arrays.equals(num1,num2)) list.add(i - len2 + 1);
        }
    
        return list;
    
        }
    }

#### 3.3最多删除一个字符得到回文 ####

[原题链接][Link 3]

给定一个非空字符串 `s`，请判断如果 **最多** 从字符串中删除一个字符能否得到一个回文字符串。

**示例 1:**

*  输入: s = “aba”
 *  输出: true

**提示:**

*  `1 <= s.length <= 105`
 *  `s` 由小写英文字母组成

**思路：** 双指针，如果遇到左右不等，那么判断左边删除一个字符，或者右边删除一个字符，继续判断是否是回文

class Solution {
        public boolean validPalindrome(String s) {
         int l = 0;
        int  r = s.length() -1;
        while (l < r){
            char c1 = s.charAt(l), c2 = s.charAt(r);
            if(c1 == c2){
    
                l++;
                r--;
    
            } else{
            
            //左边删一个字符 或者右边删一个字符
               return valid(s,l+1,r) || valid(s,l,r-1);
            }
    
        }
    
        return true;
    
    
        }
    
         boolean valid(String s, int l, int r) {
            while(l < r){
                if(s.charAt(l) != s.charAt(r)) return false;
                l++;
                r--;
            }
            return true;
            
        }
    }

#### 3.4有效的回文 ####

给定一个字符串 `s` ，验证 `s` 是否是 **回文串** ，只考虑字母和数字字符，可以忽略字母的大小写。

本题中，将空字符串定义为有效的 **回文串** 。

**示例 1:**

*  输入: s = “A man, a plan, a canal: Panama”
 *  输出: true
 *  解释：“amanaplanacanalpanama” 是回文串

**提示：**

*  `1 <= s.length <= 2 * 105`
 *  字符串 `s` 由 ASCII 字符组成

**思路：** 双指针判断是否是回文，跳过不是字母和数字的字符

**注意点：** 在大小写转化时，注意类型转换为char，而不是ASCII码

class Solution {
        
        public boolean isPalindrome(String s) {
        
            int l = 0, r = s.length() - 1; 
            while (l < r) {
        
                while (l < r && !check(s.charAt(l))) l++;
                while (l < r && !check(s.charAt(r))) r--;
                if (l < r && !isEquals(s.charAt(l), s.charAt(r))) return false;
                l++;
                r--;
            }
            return true;
        }
        public boolean check(char c) {
         //检测字符c是否为数字或字母
            return 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' || '0' <= c && c <= '9';
        }
        public boolean isEquals(char a, char b) {
         //忽略大小写比较两个字符
            if ('A' <= a && a <= 'Z') a = (char)(a + 'a' - 'A');
            if ('A' <= b && b <= 'Z') b = (char)(b + 'a' - 'A');
            return a == b;
        }
    }

#### 3.5 不含重复字符的最长子字符串 ####

[原题链接][Link 4]

给定一个字符串 `s` ，请你找出其中不含有重复字符的 **最长连续子字符串** 的长度。

**示例 1:**

*  输入: s = “abcabcbb”
 *  输出: 3
 *  解释: 因为无重复字符的最长子字符串是 “abc”，所以其长度为 3。

**提示：**

*  `0 <= s.length <= 5 * 104`
 *  `s` 由英文字母、数字、符号和空格组成

思路：滑动窗口 + set 去重

class Solution {
        
        public int lengthOfLongestSubstring(String s) {
        
    
            int len = s.length();
    
            int l = 0, r = 0;
            int max = 0;
    
            // 用于 处理去重
            Set<Character> set = new HashSet<>();
    
    
            //滑动窗口
            for (int left = 0, right = 0;  right < len; right++) {
        
    
                // 如果窗口之间存在 重复字符 就 一直移动左指针
                while(set.contains(s.charAt(right))){
        
                    set.remove(s.charAt(left));
                    left++;
                }
                set.add(s.charAt(right));
    
                max = Math.max(max, right - left + 1);
    
    
    
            }
    
            return max;
    
        }
    }

#### 3.6回文子字符串的个数 ####

[原题链接][Link 5]

给定一个字符串 `s` ，请计算这个字符串中有多少个回文子字符串。

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

**示例 1：**

*  输入：s = “abc”
 *  输出：3
 *  解释：三个回文子串: “a”, “b”, “c”

**提示：**

*  `1 <= s.length <= 1000`
 *  `s` 由小写英文字母组成

解法一：

**思路：** 中心扩散 遍历字符串，取每一个字符作为一个回文子串的中心，按照回文串的要求向两边扩散，统计回文串的个数。

**注意点：** 如果字符串是偶数那么回文子串中心有两个字符，解决方案在遍历的时候，取每一个字符的同时再取该字符与下一个字符也作为中心，向两边扩散

class Solution {
        
        char[] ch;
        int len;
        public int countSubstrings(String s) {
        
            
          ch = s.toCharArray();
          len = s.length();
          int ans = 0;
    
          for(int i = 0; i < len ;i++){
        
              ans += count(i,i);
              ans += count(i,i+1);
          }
    
               return ans;
        }
    
        int count(int i, int j){
        
            int ans = 0;
            while(i >=0 && j < len){
        
                if(ch[i] == ch[j]){
        
                    ans++;
                    i--;
                    j++;
                }else{
        
                    break;
                }
            }
    
            return ans;
        }
    }

**解法二：**

**思路：** 动态规划 `dp[i][j]`表示s的第i个字符到第j个字符能否组成回文串

当 s\[i\] 与 s\[j\] 不相同时 `dp[i][j]` 为false

当 s\[i\] 与 s\[j\] 相同时 如果下标 i 与 j 相同 那么 同一个字符符合条件，如果i 与 j 相差 1 那么由于前提条件s\[i\] 与 s\[j\] 相同 也符合条件 比如 aa

如果i 与 j 相差大于1 比如 abcda 那么判断i 到 j 区间是否是回文子串，就看 i+1 到 j- 1 是否是回文子串了 也就是 `dp[i+1][j-1]`

注意点：i 从后向前遍历 是因为 j在 i 右边 且状态必须是 有小到大 大的状态也必须包含小的状态（j 必须遍历 i遍历过的）

class Solution {
        
        public int countSubstrings(String s) {
        
       int  len = s.length();
       boolean[][] dp = new boolean[len][len];
       int res = 0;
    
       for(int i =len -1; i >=0 ; i--){
        
           for(int j = i; j < len;j++){
        
               if(s.charAt(i) == s.charAt(j) && (j- i <=1 || dp[i+1][j-1])){
        
                   dp[i][j] = true;
                   res++;
               }
           }
       }
    
       return res;
        }
    }

时间复杂度 O (n^2)

#### 3.7含有所有字符的最短字符串 ####

[原题链接][Link 6]

给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 “” 。

如果 s 中存在多个符合条件的子字符串，返回任意一个。

**注意：** 对于 `t` 中重复字符，我们寻找的子字符串中该字符数量必须不少于 `t` 中该字符数量。

**示例 1：**

*  输入：s = “ADOBECODEBANC”, t = “ABC”
 *  输出：“BANC”
 *  解释：最短子字符串 “BANC” 包含了字符串 t 的所有字符 ‘A’、‘B’、‘C’

**提示：**

*  `1 <= s.length, t.length <= 105`
 *  `s` 和 `t` 由英文字母组成

**思路:** 滑动窗口 使用两个 长度为56的数组统计字符出现的个数，使用count来记录窗口中s字符串包含 t字符串中字符的个数（有效字符）

class Solution {
        
        public String minWindow(String s, String t) {
        
             int[] num1 = new int[58];
             int[] num2 = new int[58];
    
         int len1 = s.length();
         int len2 = t.length();
    
             for(int i = 0;i < len2; i++){
        
                     num2[t.charAt(i) - 'A']++;
             }
    
    // count 记录有效字符
             int left = 0, right = 0, count = 0;
    
             String res  = "";
             while(right < len1){
        
    
               num1[s.charAt(right) - 'A']++;
               //有效字符
           if(num1[s.charAt(right) - 'A' ] <= num2[s.charAt(right) -'A']) count++;
    
           //如果 窗口中 s的某个字符 大于 t中 的 右移左窗口
           while(left <= right && num1[s.charAt(left) - 'A'] > num2[s.charAt(left) - 'A']){
        
               num1[s.charAt(left) - 'A']--;
               left++;
           }
    if(count == len2 && (res.isEmpty() || res.length() > right - left + 1)) {
        
        res = s.substring(left,right+1);
    }
    
               right++;
    
             }
    
             return res;
    
        }
    }

时间复杂度 O(n)

[Link 1]: https://leetcode.cn/problems/MPnaiL/
[Link 2]: https://leetcode.cn/problems/VabMRr/?envType=study-plan&id=lcof-ii&plan=lcof&plan_progress=4kehfu1
[Link 3]: https://leetcode.cn/problems/RQku0D/?envType=study-plan&id=lcof-ii&plan=lcof&plan_progress=4kehfu1
[Link 4]: https://leetcode.cn/problems/wtcaE1/
[Link 5]: https://leetcode.cn/problems/a7VOhD/
[Link 6]: https://leetcode.cn/problems/M1oyTv/