另参见回文子序列
哪些单词对能拼成回文串
vector<vector<int>> palindromePairs(vector<string>& words) {
// 将w1分成w1[0..cut)、w1[cut..)两段，0<=cut<=len，两种情况：
// 1. w1[0..cut)是回文，w1[cut..)是w2反转，w2+w1是回文
// 2. w1[cut..)是回文，w1[0..cut)是w2反转，w1+w2是回文
// 若w1、w2互为反转，比如abc、cba，
// abc|null + cba，处理单词abc、cut=len，返回{0,1}
// abc + null|cba，处理单词cba、cut=0， 返回{0,1}
// 这就重复了，这时用cut>0或cut<len去掉一种重复。
const int N = words.size();
unordered_map<string, int> mp; // reverse=>idx
for (int i = 0; i < N; i++) {
string reverse(words[i].rbegin(), words[i].rend());
mp[reverse] = i;
}
vector<vector<int>> ans;
for (int i = 0; i < N; i++) {
const string &word = words[i];
const int len = word.size();
for (int cut = 0; cut <= len; cut++) {
// case 1
if (isPalindrome(word, 0, cut - 1)) {
string s2 = word.substr(cut);
if (mp.count(s2) && mp[s2] != i) {
ans.push_back({mp[s2], i});
}
}
// case 2
if (isPalindrome(word, cut, len - 1)) {
string s1 = word.substr(0, cut);
if (mp.count(s1) && mp[s1] != i && cut < len) { // 用cut<len去重
ans.push_back({i, mp[s1]});
}
}
}
}
return ans;
}
bool isPalindrome(const string &s, int lo, int hi) {
while (lo < hi) {
if (s[lo++] != s[hi--]) return false;
}
return true;
}
回文数
bool isPalindrome(int x) {
// 以0结尾的正数没有回文数
if (x < 0 || (x > 0 && x % 10 == 0)) return false;
int rev = 0;
while (x > rev) {
rev = rev * 10 + x % 10;
x /= 10;
}
return rev == x || rev / 10 == x;
}
>=N的最小回文素数
int primePalindrome(int N) {
// 先生成回文，再判断是素数。因为1<=N<=10^8，只需[1..10^5)的数生成回文：
// 正反拼接（偶数位）或 正反拼接且最后一位重合（奇数位）
// 特别地，所有偶位数回文都是11的倍数
// 因为1001%11=(1111-11*10)%11=0、100001%11=(111111-1111*10)%11=0、...
// 所以abccba%11=(a*100001+b*1001*10+11*100)%11=0
// 所以偶数位回文只有11是素数回文，而11只有当8<=N<=11时才返回。
// 接下来只需判断奇数位回文
if (8 <= N && N <= 11) return 11;
for (int i = 1; i < 1e5; i++) {
string s = to_string(i);
s += string(s.rbegin() + 1, s.rend());
int x = stoi(s);
if (x >= N && isPrime(x)) return x;
}
return -1;
}
bool isPrime(int num) {
if (num <= 1) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) return false;
}
return true;
}
所有回文分割
“分割"类的标准回溯写法
vector<vector<string>> partition(string s) {
vector<vector<string>> ans;
vector<string> parts;
search(s, 0, parts, ans);
return ans;
}
void search(const string &s, int idx, vector<string> &parts, vector<vector<string>> &ans) {
const int N = s.size();
if (idx == N) {
ans.push_back(parts);
return;
}
// 尝试割下s[idx..i]
for (int i = idx; i < N; i++) {
if (!isPalindrome(s, idx, i)) continue;
parts.push_back(s.substr(idx, i - idx + 1));
search(s, i + 1, parts, ans);
parts.pop_back();
}
}
bool isPalindrome(const string &s, int l, int r) {
while (l < r) {
if (s[l++] != s[r--]) return false;
}
return true;
}
最少回文分割数
int minCut(string s) {
// 设dp[i][j]表示s[i..j]是回文串，0<=i<=j<N
// dp[i][j] = s[i]==s[j] && dp[i+1][j-1]
const int N = s.size();
vector<vector<bool>> dp(N, vector<bool>(N, false));
for (int i = N - 1; i >= 0; i--) {
for (int j = i; j < N; j++) {
dp[i][j] = s[i] == s[j];
if (i + 1 <= j - 1) dp[i][j] = dp[i][j] && dp[i+1][j-1];
}
}
// 设cut[i]表示子串s[0..i]的minCut，0<=i<N
// dp[0][i]==true时，cut[i]=0；否则，
// 对于0<=k<i的k若满足dp[k+1][i]==true，cut[i]=min{ cut[k]+1 }
vector<int> cut(N, INT_MAX);
for (int i = 0; i < N; i++) {
if (dp[0][i]) {
cut[i] = 0;
} else {
for (int k = 0; k < i; k++) {
if (dp[k+1][i]) {
cut[i] = min(cut[i], cut[k] + 1);
}
}
}
}
return cut[N-1];
}
回文排列
Given a string
s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.For example:
Given
s = "aabb", return["abba", "baab"].Given
s = "abc", return[].Hint:
- If a palindromic permutation exists, we just need to generate the first half of the string.
- To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II or Next Permutation.
vector<string> generatePalindromes(string s) {
unordered_map<char, int> mp;
int oddCnt = 0;
for (char c : s) {
mp[c]++;
if (mp[c] % 2 == 1) oddCnt++;
else oddCnt--;
}
if (oddCnt > 1) return {};
string odd, half;
for (auto &e : mp) {
if (e.second % 2 == 1) odd = string(1, e.first);
half += string(e.second / 2, e.first);
}
vector<string> ans;
permute(half, 0, odd, ans);
return ans;
}
void permute(string &half, int idx, const string &odd, vector<string> &ans) {
if (idx == half.size()) {
ans.push_back(half + odd + string(half.rbegin(), half.rend()));
return;
}
unordered_set<char> seen; // 防止相同元素再次交换
for (int i = idx; i < half.size(); i++) {
if (seen.count(half[i])) continue;
seen.insert(half[i]);
swap(half[i], half[idx]);
permute(half, idx + 1, odd, ans);
swap(half[i], half[idx]);
}
}
对称数
旋转180度看上去一样的数叫对称数。求在[low, high]范围内对称数的个数
class Solution {
unordered_map<string, string> mp = { {"0","0"}, {"1","1"}, {"6","9"}, {"8","8"}, {"9","6"} };
public:
int strobogrammaticInRange(string low, string high) {
int count = 0;
expand("", low, high, count); // n%2==0
for (string s : {"0", "1", "8"}) { // n%2==1
expand(s, low, high, count);
}
return count;
}
// 扩展num两端，添加数对
void expand(string num, const string &low, const string &high, int &count) {
const int len = num.size(), lowLen = low.size(), highLen = high.size();
if (len > highLen) return; // 排除过长的
if (len >= lowLen && !(len > 1 && num[0] == '0')) { // 长度合适，排除以‘0’开头的
if (lowLen == highLen) {
if (low <= num && num <= high) count++;
} else {
if ((len == lowLen && num >= low) || (len == highLen && num <= high)
|| (lowLen < len && len < highLen)) count++;
}
}
for (auto &e : mp) {
expand(e.first + num + e.second, low, high, count);
}
}
};