字符串专题

文章目录

字符串专题
- 一，字符串匹配算法
- - - 暴力匹配BF
    - KMP字符串匹配
- 二，leetcode字符串题解
- - 统计词频相关
  - - 1.赎金信
    - 2.字符串中第一个唯一字符
    - 3.学生出勤记录
  - 字符串反转相关
  - - 1.反转字符串I
    - 2.反转字符串II
  - 回文串相关
  - - 1.验证回文串
    - 2.验证回文串II
    - 3.最长回文子串
    - 4.回文字串

一，字符串匹配算法

所谓字符串匹配就是给定一个模式串和文本串，判定模式串是否是文本串的一个字串，并返回模式串在文本串中开始出现的位置

暴力匹配BF

/**
     * 暴力解法
     * O(MN)
     *
     * @param txt
     * @param pat
     * @return
     */
    public static int forceSearch(String txt, String pat) {
        int txtLen = txt.length();
        int patLen = pat.length();
        int i = 0;
        int j = 0;
        while (i < txtLen && j < patLen) {
            //逐一比对
            if (txt.charAt(i) == pat.charAt(j)) {
                //比对成功，继续向后
                i++;
                j++;
            } else {
                //比对失败，j回到模式串开始，i回到上一次比对位置的下一个位置
                j = 0;
                i = i - j + 1;
            }
        }
        if (j == patLen) {
            return i - j;
        } else {
            return -1;
        }
    }

KMP字符串匹配

public int kmpSearch(String txt, String pat, int[] next) {
        int txtLen = txt.length();
        int patLen = pat.length();
        int i = 0;
        int j = 0;
        while (i < txtLen && j < patLen) {
            if (j == -1 || txt.charAt(i) == pat.charAt(j)) {
                //匹配则继续比较下一个元素
                j++;
                i++;
            } else {
                //不匹配则将模式串移动到以对应next数组元素为索引的位置
                j = next[j];
            }
        }
        if (j == patLen) {
            return i - j;
        } else {
            return -1;
        }
    }
    /**
     * 寻找前缀后缀最长公共元素长度
     * 获取next数组，告知下一次应该跳到模式串的哪一个位置
     *
     * @param patStr
     * @param next
     */
    public void next(String patStr, int[] next) {
        int length = patStr.length();
        next[0] = -1;
        //指向前边公共前缀的指针
        int k = -1;
        //遍历时指向当前字符的指针
        int j = 0;
        //这里其实用到了动态规划的思想
        while (j < length - 1) {
            if (k == -1 || patStr.charAt(k) == patStr.charAt(j)) {
                ++k;
                ++j;
                next[j] = k;
            } else {
                k = next[k];
            }
        }
    }

二，leetcode字符串题解

统计词频相关

1.赎金信

在这里插入图片描述

其实这道题目的意思就是，给定两个字符串A和B，判断B中的的字符能否构成A，这时候我们只需要统计出B的字符和其出现的频次，然后在A中看能否够用即可

public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character,Integer> map = new HashMap<>();
        //统计magazine中各个字符出现的次数
        for(Character c : magazine.toCharArray()){
            map.put(c , map.getOrDefault(c,0) + 1);
        }
        //遍历过程中，判断map中有没有ransomNote需要字符，有则还需判断还够不够其所需
        for(Character c : ransomNote.toCharArray()){
            if(map.containsKey(c) && map.get(c) != 0){
                map.put(c,map.get(c) - 1);
            }else{
                return false;
            }
        }
        return true;
    }

2.字符串中第一个唯一字符

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QSspdxcw-1573918895663)(C:\Users\12642\AppData\Roaming\Typora\typora-user-images\image-20191116152348466.png)]

也是基于统计词频，返回第一个词频为1的即可

/**
     * 字符串中第一个唯一字符
     * @param s
     * @return
     */
    public int firstUniqChar(String s) {
        Map<Character,Integer> map = new HashMap<>();
        //统计词频率
        for(Character c : s.toCharArray()){
            map.put(c,map.getOrDefault(c,0) + 1);
        }
        //按序遍历找出第一个唯一的字符
        for(Character c : s.toCharArray()){
            if(map.containsKey(c) && map.get(c) == 1){
                return s.indexOf(c);
            }
        }
        return -1;
    }

3.学生出勤记录

在这里插入图片描述

public boolean checkRecord(String s) {
        //连续迟到2次以上
        if(s.indexOf("LLL") != -1){
            return false;
        }
        int Asum = 0;
        //统计词频率
        for(Character c : s.toCharArray()) {
            if(c == 'A'){
                Asum++;
            }
            //超过1个A
            if(Asum > 1){
                return false;
            }
        }
        return true;
    }

字符串反转相关

1.反转字符串I

在这里插入图片描述

双指针，一个从前往后，一个从后往前，边遍历边交换

public void reverseString(char[] s) {
        //双指针法
        int start = 0;
        int end = s.length - 1;
        if(start == end){
            return;
        }
        while(start < end){
            char c = s[start];
            s[start] = s[end];
            s[end] = c;
            start++;
            end--;
        } 
    }

2.反转字符串II

在这里插入图片描述

public String reverseStr2(String s, int k) {
        int n = s.length();
        //反转轮次
        int time = 1;
        char[] chars = s.toCharArray();
        for(int i = 0;i < n;){
            //记录每一轮次的结束字符的索引
            int j = Math.min(n,time * 2 * k);
            //记录剩余字符个数
            int rest = j - i;
            if(rest >= k){
                //剩余字符多余k个，则反转前k个
                reverse(chars,i,i + k - 1);
            }else{
                //否则将剩余的所有全部反转
                reverse(chars,i,j - 1);
            }
            i = j;
            time++;
        }
        return String.valueOf(chars);
    }
    public void reverse(char[] s,int i,int j) {
        //双指针法
        int start = i;
        int end = j;
        if(start == end){
            return;
        }
        while(start < end){
            char c = s[start];
            s[start] = s[end];
            s[end] = c;
            start++;
            end--;
        }
    }

回文串相关

1.验证回文串

在这里插入图片描述

/**
    * 验证回文串
    * @param s
    * @return
    */
   public boolean isPalindrome(String s) {
       s = s.toLowerCase();
       s = s.replaceAll("[^0-9a-z]","");
       int start = 0;
       int end = s.length() - 1;
       char[] chars = s.toCharArray();
       while(start < end){
           if(chars[start] != chars[end]){
               return false;
           }else{
               start++;
               end--;
           }
       }
       return true;
   }

2.验证回文串II

在这里插入图片描述

public boolean validPalindrome(String s) {
        s = s.toLowerCase();
        s = s.replaceAll("[^0-9a-z]","");
        int start = 0;
        int end = s.length() - 1;
        char[] chars = s.toCharArray();
        while(start < end){
            if(chars[start] != chars[end]){
                return isValid(s,start,end - 1) || isValid(s,start + 1,end);
            }else{
                start++;
                end--;
            }
        }
        return true;
    }
    public boolean isValid(String s, int i, int j){
        while(i < j){
            if(s.charAt(i) != s.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

3.最长回文子串

在这里插入图片描述

动态规划解法：

/**
     * 最长回文子串
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int len = s.length();
        if(len <= 1){
            return s;
        }
        boolean[][] dp = new boolean[len][len];
        //记录最长回文串长度
        int longestPalindromeLen = 1;
        //记录最长的回文串
        String longestPalindrome = s.substring(0,1);
        //右边界
        for(int r = 1;r < len;r++){
            //左边界
            for(int l = 0;l < r;l++){
                //动态转移方程：
                //          dp[l][r]:表示从l到r的字串是否是回文串
                //          dp[l][r]如果是回文串的话那么 dp[l + 1][r - 1]必定是回文串
                //          还有一种情况，如果类似 aba这种，当我l+1,r-1区间收缩后，就只剩下b，b肯定是回文串，
                //                       又或者类似aa这种，收缩后没有字符，也肯定是回文串，则说明，如果区间[l,r]之间少于1个元素，则肯定回文
                //          所以：r - l <= 2也回文
                // if(s[l] == s[r] &&( r - l <= 2 || dp[l + 1][r - 1])
                //      dp[l][r] = true
                if(s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])){
                    //改变状态
                    dp[l][r] = true;
                    //记录长度
                    if(r - l + 1 > longestPalindromeLen){
                        longestPalindromeLen = r - l + 1;
                        longestPalindrome = s.substring(l,r + 1);
                    }
                }
            }
        }
        return longestPalindrome;
    }

4.回文字串

在这里插入图片描述

暴力解法：

/**
     * 回文字串数量
     * @param s
     * @return
     */
    public int countSubstrings(String s) {
        int len = s.length();
        //记录回文字串数量
        int res = 0;
        //暴力遍历判断所有字串，每一个子串区间[i,j]
        for(int i = 0;i < len;i++){
            for(int j = i;j < len;j++){
                boolean b = true;
                int ii = i;
                int jj = j;
                //判断是否回文
                while(ii < jj){
                    if(s.charAt(ii) != s.charAt(jj)){
                        b = false;
                        break;
                    }else{
                        ii++;
                        jj--;
                    }
                }
                if(b){
                    res++;
                }
            }
        }
        return res;
    }

动态规划解法：

/**
     * 动态规划
     * @param s
     * @return
     */
    public int countSubstrings1(String s) {
        char[] charArr = s.toCharArray();
        int n = charArr.length;
        int count = 0;
        boolean dp[][] = new boolean[n][n];
        //从后往前遍历
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (charArr[i] == charArr[j] && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }
        return count;
    }