题目场景: 2022.10.16 亚信安全笔试

😘最长回文子串

题库链接:
|力扣: leetcode.cn|LeetCode: leetcode.com|

题目: 给你一个字符串 s，找到 s 中最长的回文子串。

解析: 采用两种思路可以解决: 动态规划 和 中心扩散

动态规划

通过分析可知, 当第i个字符到第j个字符为回文串的同时, 如果i-1位于j+1位相同, 此时第i-1位到j+1位仍为回文串, 根据此内容进行动态规划, 可写出如下代码:

class Solution {
        public String longestPalindrome(String s) {
            int n = s.length();
            if (n < 2) return s;

            int begin = 0;
            int end = 0;
            boolean[][] dp = new boolean[n][n];
            for (int i = 0; i < n; i++) {
                dp[i][i] = true;
            }

            char[] chars = s.toCharArray();
            int j;
            for (int len = 2; len <= n; len++) {
                for (int i = 0; i < n; i++) {
                    j = i + len - 1;
                    if (j >= n) break;
                    if (chars[i] != chars[j]) dp[i][j] = false;
                    else if (len < 4) dp[i][j] = true;
                    else dp[i][j] = dp[i + 1][j - 1];

                    if (dp[i][j] && len > (end - begin + 1)) {
                        begin = i;
                        end = j;
                    }
                }
            }
            return s.substring(begin, end + 1);
        }

中心扩散

第二种思路同样基于状态转移方程, 不过于动态规划的广度优先不同, 本方法通过不断修改中心点, 尽可能得到每个点的最长回文串, 当左右相同时,则继续向外扩展

 class Solution {
        public String longestPalindrome(String s) {
            if (s.length() < 2) return s;

            int begin = 0, end = 0;
            for (int i = 0; i < s.length(); i++) {
                int len1 = expendCenter(s, i, i);
                int len2 = expendCenter(s, i, i + 1);
                int len = Math.max(len1, len2);
                if (len > end - begin) {
                    begin = i - (len - 1) / 2;
                    end = i + len / 2;
                }
            }
            return s.substring(begin, end + 1);
        }

        private int expendCenter(String s, int i, int j) {
            while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
                i--;
                j++;
            }
            return j - i - 1;
        }
    }

🥰正则表达式匹配

题库链接:
|力扣: leetcode.cn|LeetCode: leetcode.com|

题目:
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 “.” 和 “*” 的正则表达式

“.” 匹配任意单个字符
“*” 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

解析: 采用动态规划解决此题

动态规划

当p的j位字符为正常字符或者点号时, 只要能与s的i位匹配, 则两者的匹配状态等同于前i-1和前j-1位字符串的匹配状态, 如果这两位不匹配则直接返回不匹配即可

对于p的j位字符为星号时,需要分类判断
若p的j位字符为星号, 则p的j-1位可以出现0次或多次

• 若出现0次, 则是否匹配取决于p的前j-2与s是否匹配
  例如s=abc和p=abcd*
• 若出现多次, 则首先判断s的最后一位是否匹配p的允许多次出现的字符, 即j-1位
  例如s=abcddd和p=abcd*
  若该位匹配则状态等同于s的前i-1位与p的匹配状态
  如s=abcdd和p=abcd*
  直至s=abc和p=abcd*, 这时等同于出现0次

    class Solution {
        public boolean isMatch(String s, String p) {
            int m = s.length();
            int n = p.length();

            boolean[][] dp = new boolean[m + 1][n + 1];
            dp[0][0] = true;
            for (int i = 0; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (p.charAt(j - 1) == '*') {
                        dp[i][j] = dp[i][j - 2];
                        if (match(s, p, i, j - 1)) {
                            dp[i][j] = dp[i][j] || dp[i - 1][j];
                        }
                    } else {
                        if (match(s, p, i, j))
                            dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
            return dp[m][n];
        }

        private boolean match(String s, String p, int i, int j) {
            if (i == 0) {
                return false;
            }
            if (p.charAt(j - 1) == '.') {
                return true;
            }
            return s.charAt(i - 1) == p.charAt(j - 1);
        }
    }