Palindrome
5. Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
这一题是很多题目的基础, 最长回文串
class Solution {
public:
string longestPalindrome(string s) {
if (s.size() < 2)
return s;
int len = s.size(), max_left = 0, max_len = 1, left, right;
for (int start = 0; start < len && len - start > max_len / 2;) {
left = right = start;
while (right < len - 1 && s[right + 1] == s[right])
++right;
start = right + 1;
while (right < len - 1 && left > 0 && s[right + 1] == s[left - 1]) {
++right;
--left;
}
if (max_len < right - left + 1) {
max_left = left;
max_len = right - left + 1;
}
}
return s.substr(max_left, max_len);
}
};
214. Shortest Palindrome
Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation. For example: Given "aacecaaa", return "aaacecaaa". Given "abcd", return "dcbabcd".
暴力解:
class Solution {
public:
string shortestPalindrome(string s) {
int len = s.size();
if (len <= 1) return s;
string reversed(s);
reverse(reversed.begin(), reversed.end());
for (int i = 0; i < s.size(); ++i) {
if (reversed.substr(i) == s.substr(0, len - i)) {
return reversed.substr(0, i) + s;
}
}
return s;
}
};
336. Palindrome Pairs
Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.
Example 1: Given words = ["bat", "tab", "cat"] Return [[0, 1], [1, 0]] The palindromes are ["battab", "tabbat"] Example 2: Given words = ["abcd", "dcba", "lls", "s", "sssll"] Return [[0, 1], [1, 0], [3, 2], [2, 4]] The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]
class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
unordered_map<string, int> word2idx;
vector<vector<int>> res;
for (size_t i = 0; i < words.size(); ++i) {
word2idx[words[i]] = i;
}
for (int i = 0; i < words.size(); ++i) {
for (size_t j = 0; j <= words[i].size(); ++j) {
auto left = words[i].substr(0,j);
auto right = words[i].substr(j);
auto rl = left;
auto rr = right;
reverse(rl.begin(), rl.end());
reverse(rr.begin(), rr.end());
if (word2idx.find(rl) != word2idx.end() && isPalindrome(right) && word2idx[rl] != i) {
res.push_back({i, word2idx[rl]});
}
if (j > 0 && word2idx.find(rr) != word2idx.end() && isPalindrome(left) && word2idx[rr] != i) {
res.push_back({word2idx[rr], i});
}
}
}
return res;
}
bool isPalindrome(const string& s) {
int len = s.size();
if (len <= 1) return true;
int i = 0;
int j = len - 1;
while (i < j) {
if(s[i++] != s[j--]) return false;
}
return true;
}
};
7. Reverse Integer
Reverse digits of an integer.
Example1: x = 123, return 321 Example2: x = -123, return -321
class Solution {
public:
int reverse(int x) {
if (x == 0) return 0;
int sign = x > 0;
long long data = labs(x);
long long reversed = 0;
while (data) {
reversed = reversed * 10 + (data % 10);
data /= 10;
}
if (!sign) reversed *= -1;
if (reversed > INT_MAX || reversed < INT_MIN) return 0;
return static_cast<int>(reversed);
}
};
9. Palindrome Number
Determine whether an integer is a palindrome. Do this without extra space.
class Solution {
public:
bool isPalindrome(int x) {
if (x<0) return false;
long long reversed = 0;
long long data = x;
while (x) {
reversed = reversed*10 + (x % 10);
x /= 10;
}
return reversed == data;
}
};
234. Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
Follow up: Could you do it in O(n) time and O(1) space?
基本想法是找到中点,然后翻转后半部分
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (!head || !head->next) return true;
ListNode* slow = head;
ListNode* fast = head;
ListNode* pre = nullptr;
while (fast && fast->next) {
fast = fast->next->next;
pre = slow;
slow = slow->next;
}
ListNode* l2 = slow;
pre->next = nullptr;
l2 = reverseList(l2);
while (head && l2) {
if (head->val != l2->val) return false;
head = head->next;
l2 = l2->next;
}
return true;
}
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* cur = head;
ListNode* next = head->next;
cur->next = nullptr;
ListNode* newHead = reverseList(next);
next->next = cur;
return newHead;
}
};
Recursive solution.
An easy understanding would be using a stack instead, since both of them using O(N) space, explicitly or implicitly.
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* cur = head;
return isEqual(head, &cur);
}
bool isEqual(ListNode* head, ListNode** cur) {
if (!head) return true;
bool isPal = isEqual(head->next, cur) && ((*cur)->val == head->val);
(*cur) = (*cur)->next;
return isPal;
}
};
131. Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. For example, given s = "aab", Return [ ["aa","b"], ["a","a","b"] ]
class Solution {
public:
vector<vector<string>> partition(string s) {
unordered_map<string, vector<vector<string>>> memo;
vector<vector<string>> res;
std::function<vector<vector<string>>(string& )> dfs = [&](string& str) {
if (memo.find(str) != memo.end()) return memo[str];
if (isPalindrome(str, 0, str.size() - 1)) {
res.push_back({str});
}
for (int i = 1; i < str.size(); ++i) {
if (isPalindrome(str, 0, i)) {
auto left = str.substr(0, i);
auto right = str.substr(i);
auto ret = dfs(right);
for (auto lst : ret) {
res.push_back({left});
for (auto str : lst) res.back().push_back(str);
}
}
}
memo[str] = res;
return res;
};
return dfs(s);
}
bool isPalindrome(const string& s, int i, int j) {
if (j - i <= 1) return true;
while (i < j) {
if (s[i++] != s[j--]) return false;
}
return true;
}
};
132. Palindrome Partitioning II
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab", Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
class Solution {
public:
int minCut(string s) {
size_t len = s.size();
vector<int> dp(len+1);
for (size_t i = 0; i < len + 1; ++i) dp[i] = i - 1;
for (int i = 0; i < len; ++i) {
for (int j = 0; j <= i && i + j < len && s[i-j] == s[i+j]; ++j)
dp[i+j+1] = min(dp[i+j+1], 1 + dp[i-j]);
for (int j = 1; i -j + 1 >= 0 && j + i < len && s[i-j+1] == s[i+j]; ++j)
dp[i+j+1] = min(dp[i+j+1], 1 + dp[i-j+1]);
}
return dp[len];
}
};
214. Shortest Palindrome
Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given "aacecaaa", return "aaacecaaa". Given "abcd", return "dcbabcd".
brute force solution:
class Solution {
public:
string shortestPalindrome(string s) {
int len = s.size();
if (len <= 1) return s;
string reversed(s);
reverse(reversed.begin(), reversed.end());
for (int i = 0; i < s.size(); ++i) {
if (reversed.substr(i) == s.substr(0, len - i)) {
return reversed.substr(0, i) + s;
}
}
return s;
}
};
246 Strobogrammatic Number
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to determine if a number is strobogrammatic. The number is represented as a string. For example, the numbers "69", "88", and "818" are all strobogrammatic.
class Solution {
public:
bool isStrobogrammatic(string nums) {
if (nums.size() == 0) return true;
unordered_map<char, char> dict{{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
int i = 0;
int j = nums.size() - 1;
while (i <= j) {
if (dict.find(nums[i]) == dict.end() || dict.find(nums[j]) == dict.end()) return false;
if (nums[i] != dict[nums[j]] || nums[j] != dict[nums[i]]) return false;
++i;
--j;
}
return true;
}
};
247 Strobogrammatic Number II
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Find all strobogrammatic numbers that are of length = n.
For example, Given n = 2, return ["11","69","88","96"].
class Solution {
public:
vector<string> findStrobogrammatic(int n) {
return findStrobogrammatic(n, n);
}
vector<string> findStrobogrammatic(int n, int m) {
if (n <= 0) return {""};
if (n == 1) return {"0", "1", "8"};
auto prev = findStrobogrammatic(n - 2, m);
vector<string> res;
for (auto str : prev) {
if (n != m)
res.push_back("0" + str + "0");
res.push_back("1" + str + "1");
res.push_back("6" + str + "9");
res.push_back("8" + str + "8");
res.push_back("9" + str + "6");
}
return res;
}
};
class Solution_v2 {
public:
vector<string> findStrobogrammatic(int n) {
vector<vector<char>> pairs = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
vector<string> res;
string slu(n, '0');
function<void(string&, int, int)> dfs =
[&](string& str, int left, int right) {
if (left > right) {
res.push_back(str);
// cout << str << endl;
return;
}
for (auto p : pairs) {
str[left] = p[0];
str[right] = p[1];
if (str.length() != 1 && str[0] == '0') continue;
if (left < right || (left == right && p[0] == p[1]))
dfs(str, left+1, right-1);
}
};
dfs(slu, 0, n-1);
return res;
}
};
248 Strobogrammatic Number III
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high. For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.
Note: Because the range might be a large number, the low and high numbers are represented as string.
class Solution {
public:
int strobogrammaticInRange(string low, string high) {
int count = 0;
vector<vector<int>> pairs = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
for (auto len = low.size(); len <= high.size(); ++len) {
string str(len, '0');
dfs(low, high, str, 0, len - 1, count, pairs);
}
return count;
}
void dfs(string& low, string& high, string& str, int left, int right, int& count, vector<vector<int>>& pairs) {
if (left > right) {
if ((str.length() == low.length() && str < low) ||
(str.length() == high.length() && str > high)) return;
cout << str << endl;
count++;
return;
}
for (auto p : pairs) {
str[left] = p[0];
str[right] = p[1];
if (str.length() != 1 && str[0] == '0') continue;
if (left < right || (left == right && p[0] == p[1]))
dfs(low, high, str, left + 1, right - 1, count, pairs);
}
}
};
267 Palindrome Permutation II
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 [].
class Solution {
public:
vector<string> generatePalindromes(string s) {
vector<string> res;
unordered_map<char, int> char_cnt;
for (auto c : s) {
char_cnt[c]++;
}
char single;
int single_cnt = 0;
for (auto kv : char_cnt) {
if (kv.second & 1) {
single = kv.first;
single_cnt++;
}
if (single_cnt > 1) return res;
}
string slu;
if (single_cnt) {
slu = single;
char_cnt[single]--;
}
string charset;
for (auto kv : char_cnt) {
while (kv.second) {
kv.second -= 2;
charset += kv.first;
}
}
dfs(charset, res, slu, 0);
return res;
}
void dfs(string charset, vector<string>& res, string slu,int index) {
if (charset.size() == index) {
string ret = charset;
reverse(ret.begin(), ret.end());
slu = charset + slu + ret;
res.push_back(slu);
return;
}
for (int i = index; i < charset.size(); ++i) {
if (i != index && charset[i] == charset[index]) continue;
swap(charset[i], charset[index]);
dfs(charset, res, slu, index + 1);
}
}
};