# Untitled

unknown
plain_text
3 years ago
3.2 kB
7
Indexable
Never
```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];
}
};```