Untitled

https://leetcode.com/problems/longest-palindromic-substring/
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        bool palindrome[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                palindrome[i][j] = false;
            }
        }
        for (int i = 1; i <= n; i++) {
            palindrome[i][i] = true;
        }
        for (int i = 1; i < n; i++) {
            if (s[i - 1] == s[i]) {
                palindrome[i][i + 1] = true;
            }
        }
        for (int i = n; i > 0; i--) {
            for (int j = i + 2; j <= n; j++) {
                if (s[i - 1] == s[j - 1]) {
                    palindrome[i][j] |= palindrome[i + 1][j - 1];
                }
            }
        }
        int max_len = 0;
        int start = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                if (palindrome[i][j] && j - i + 1 > max_len) {
                    max_len = j - i + 1;
                    start = i - 1;
                }
            }
        }
        return s.substr(start, max_len);
    }
};


https://leetcode.com/problems/palindrome-partitioning-ii/
class Solution {
public:
    int minCut(string s) {
        int n = s.length();
        bool palindrome[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                palindrome[i][j] = false;
            }
        }
        for (int i = 1; i <= n; i++) {
            palindrome[i][i] = true;
        }
        for (int i = 1; i < n; i++) {
            if (s[i - 1] == s[i]) {
                palindrome[i][i + 1] = true;
            }
        }
        for (int i = n; i > 0; i--) {
            for (int j = i + 2; j <= n; j++) {
                if (s[i - 1] == s[j - 1]) {
                    palindrome[i][j] |= palindrome[i + 1][j - 1];
                }
            }
        }
        int mincuts[n + 1];
        mincuts[0] = 0;
        for (int i = 1; i <= n; i++) {
            mincuts[i] = i;
            for (int j = 0; j < i; j++) {
                if (palindrome[j + 1][i]) {
                    mincuts[i] = min(mincuts[i], mincuts[j] + 1);
                }
            }
        }
        return mincuts[n] - 1;
    }
};


https://leetcode.com/problems/regular-expression-matching/
class Solution {
public:
    bool isMatch(string s, string p) {
        int slen = s.length();
        int plen = p.length();
        
        bool dp[slen + 1][plen + 1];
        for (int i = 0; i <= slen; i++) {
            for (int j = 0; j <= plen; j++) {
                dp[i][j] = false;
            }
        }
        dp[slen][plen] = true;
        
        for (int i = slen; i >= 0; i--) {
            for (int j = plen - 1; j >= 0; j--) {
                bool is_start_same = (i < slen && (s[i] == p[j] || p[j] == '.'));
                if (j + 1 < plen && p[j + 1] == '*') {
                    dp[i][j] |= dp[i][j + 2];
                    dp[i][j] |= (is_start_same && dp[i + 1][j]);
                } else if (is_start_same) {
                    dp[i][j] |= dp[i + 1][j + 1];
                }
            }
        }
        return dp[0][0];
    }
};