String
12. Valid Palindrome
class Solution {
public:
bool isPalindrome(string s) {
string trimmed;
for (char c : s) {
if (isalnum(c)) {
trimmed += tolower(c);
}
}
string reversed = trimmed;
std::reverse(reversed.begin(), reversed.end());
return trimmed == reversed;
}
};class Solution {
public boolean isPalindrome(String s) {
String trimmed = "";
String lower = s.toLowerCase();
for (char c : lower.toCharArray()) {
if (Character.isLetterOrDigit(c)) {
trimmed += c;
}
}
String reversed = new StringBuilder(trimmed).reverse().toString();
return trimmed.equals(reversed);
}
}class Solution {
public:
bool isAnagram(string s, string t) {
vector<int> v(26, 0);
for (char c : s) {
v[c-'a']++;
}
for (char c : t) {
v[c-'a']--;
}
for (int i : v) {
if (i != 0) {
return false;
}
}
return true;
}
};class Solution {
public boolean isAnagram(String s, String t) {
int[] v = new int[26];
for (char c : s.toCharArray()) {
v[c - 'a']++;
}
for (char c : t.toCharArray()) {
v[c - 'a']--;
}
for (int i : v) {
if (i != 0) {
return false;
}
}
return true;
}
}class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLength = 0, left = 0, right = 0;
HashSet<Character> cache = new HashSet<>();
for (;right < s.length(); right++) {
char c = s.charAt(right);
if (cache.contains(c)) {
do {
char l = s.charAt(left);
cache.remove(l);
left++;
} while (cache.contains(c));
cache.add(c);
} else {
cache.add(c);
maxLength = Math.max(maxLength, cache.size());
}
}
return maxLength;
}
}# https://leetcode.com/problems/minimum-window-substring/solutions/
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.length();
int maxLength = 0;
unordered_set<char> charSet;
int left = 0;
for (int right = 0; right < n; right++) {
if (charSet.count(s[right]) == 0) {
charSet.insert(s[right]);
maxLength = max(maxLength, right - left + 1);
} else {
while (charSet.count(s[right])) {
charSet.erase(s[left]);
left++;
}
charSet.insert(s[right]);
}
}
return maxLength;
}
};class Solution {
public:
int longestPalindrome(string s) {
unordered_map<char, int> map;
for (char &c : s) {
map[c]++;
}
int result = 0;
bool flag = false;
for (auto& p : map) {
if (p.second % 2 == 0) {
result += p.second;
} else {
result += p.second - 1;
flag = true;
}
}
return (flag) ? result + 1 : result;
}
};class Solution {
public int longestPalindrome(String s) {
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
int result = 0;
boolean flag = false;
for (Map.Entry<Character, Integer> e : map.entrySet()) {
if (e.getValue() % 2 == 0) {
result += e.getValue();
} else {
result += e.getValue() - 1;
flag = true;
}
}
return flag ? result + 1 : result;
}
}// https://leetcode.com/problems/minimum-window-substring/solutions/26808/here-is-a-10-line-template-that-can-solve-most-substring-problems/
class Solution {
public:
string minWindow(string s, string t) {
vector<int> v(128, 0);
for (auto c : t) v[c]++;
int counter = t.size(), begin = 0, end = 0, d = INT_MAX, head = 0;
while (end < s.size()) {
if (v[s[end++]]-- > 0) counter--;
while (counter == 0) {
if (end - begin < d) d = end - (head = begin);
if (v[s[begin++]]++ == 0) counter++;
}
}
return d == INT_MAX ? "" : s.substr(head, d);
}
};class Solution {
public String minWindow(String s, String t) {
int[] v = new int[128];
int counter = t.length(), begin = 0, end = 0, d = Integer.MAX_VALUE, head = 0;
for (char c : t.toCharArray()) {
v[c]++;
}
char[] sa = s.toCharArray();
while (end < sa.length) {
if (v[sa[end++]]-- > 0) {
counter--;
}
while (counter == 0) {
if (end - begin < d) {
d = end - begin;
head = begin;
}
if (v[sa[begin++]]++ == 0) {
counter++;
}
}
}
return d == Integer.MAX_VALUE ? "" : s.substring(head, head+d);
}
}class Solution {
public:
int myAtoi(string s) {
int i = 0;
int sign = 1;
long ans = 0;
while (i < s.length() && s[i] == ' ') {
i++;
}
if (s[i] == '-') {
sign = -1;
i++;
} else if (s[i] == '+') {
i++;
}
while (i < s.length()) {
if (s[i] >= '0' && s[i] <= '9') {
ans = ans*10 + (s[i] - '0');
if (ans > INT_MAX && sign == -1) {
return INT_MIN;
} else if (ans > INT_MAX && sign == 1) {
return INT_MAX;
}
i++;
} else {
return ans * sign;
}
}
return ans * sign;
}
};https://leetcode.com/problems/longest-palindromic-substring/solutions/4212564/beats-96-49-5-different-approaches-brute-force-eac-dp-ma-recursion/
class Solution {
public String longestPalindrome(String s) {
return solution5(s);
}
// [Manacher Algorithm](https://www.youtube.com/watch?v=h_fSaWvxD2Y)
// https://www.youtube.com/watch?v=Dg0EP43jTXg
private String solution1(String s) {
if (s == null || s.length() <= 1) {
return s;
}
char[] chars = s.toCharArray();
char[] newChars = toNewCharArray(chars);
int[] results = new int[newChars.length];
int center = 0;
int right = 0;
for (int i = 1; i < newChars.length - 1; i++) {
int i_mirror = 2*center-i;
if (i < right) {
results[i] = Math.min(right - i, results[i_mirror]);
}
while(newChars[i+results[i]+1] == newChars[i-results[i]-1]) {
results[i]++;
}
if (i+results[i] > right) {
center = i;
right = i+ results[i];
}
}
int maxLength = 0;
int maxIndex = 0;
for (int i = 1; i < newChars.length - 1; i++) {
if (results[i] > maxLength) {
maxLength = results[i];
maxIndex = i;
}
}
int start = (maxIndex - maxLength) / 2;
//return s.substring(start, start+maxLength);
return new String(chars, start, maxLength);
}
private char[] toNewCharArray(char[] chars) {
char[] newChars = new char[chars.length*2+3];
int index = 0;
newChars[index++] = '^';
for (int i = 0; i < chars.length; i++) {
newChars[index++] = '#';
newChars[index++] = chars[i];
}
newChars[index++] = '#';
newChars[index] = '$';
return newChars;
}
// brute force
private String solution2(String s) {
if (s == null || s.length() <= 1) {
return s;
}
int n = s.length();
int maxLen = 0;
int maxStart = 0;
for (int start = 0; start < n; start++) {
// note here is len = maxLen+1 > maxlen for sure, and end <= n
for (int end = start+maxLen; end < n; end++) {
String sub = s.substring(start, end+1);
if (isPalindrom(sub)) {
maxLen = sub.length();
maxStart = start;
}
}
}
return s.substring(maxStart, maxStart+maxLen);
}
private boolean isPalindrom(String s) {
String reversed = new StringBuilder(s).reverse().toString();
return reversed.equals(s);
}
// recursive
private String solution3(String s) {
if (isPalindrom(s)) {
return s;
}
String left = solution3(s.substring(0, s.length()-1));
String right = solution3(s.substring(1));
if (left.length() > right.length()) {
return left;
} else {
return right;
}
}
// dp
private String solution4(String s) {
if (s == null || s.length() <= 1) {
return s;
}
int n = s.length();
int maxLen = 1;
int maxStart = 0;
boolean[][] dp = new boolean[n][n];
for (int end = 0; end < s.length(); end++) {
dp[end][end] = true;
for (int start = 0; start < end; start++) {
if (s.charAt(start) == s.charAt(end) && (end - start <= 2 || dp[start+1][end-1])) {
dp[start][end] = true;
if (end - start + 1 > maxLen) {
maxLen = end - start + 1;
maxStart = start;
}
}
}
}
return s.substring(maxStart, maxStart+maxLen);
}
// expand from middle
private String solution5(String s) {
if (s == null || s.length() <= 1) {
return s;
}
String maxStr = s.substring(0, 1);
for (int i = 0; i < s.length(); i++) {
String odd = expandingFromCenter(s, i, i);
String even = expandingFromCenter(s, i, i+1);
if (odd.length() > maxStr.length()) {
maxStr = odd;
}
if (even.length() > maxStr.length()) {
maxStr = even;
}
}
return maxStr;
}
private String expandingFromCenter(String s, int left, int right) {
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return s.substring(left+1, right);
}
}class Solution {
private:
static const int SIZE = 26;
bool isAnagram(int (&sa)[], int (&pa)[]) {
for (int i = 0; i < SIZE; i++) {
if (sa[i] != pa[i]) {
return false;
}
}
return true;
}
public:
vector<int> findAnagrams(string s, string p) {
int sa[SIZE] = {0};
int pa[SIZE] = {0};
for (int i = 0; i < p.length(); i++) {
++pa[p[i]-'a'];
}
vector<int> res;
int left = 0;
for (int right = 0; right < s.length(); right++) {
++sa[s[right]-'a'];
if (right-left+1 < p.length()) {
continue;
} else {
if (isAnagram(sa, pa)) {
res.push_back(left);
}
--sa[s[left]-'a'];
left++;
}
}
return res;
}
};class Solution {
private static final int SIZE = 26;
public List<Integer> findAnagrams(String s, String p) {
int[] sa = new int[SIZE];
int[] pa = new int[SIZE];
for (int i = 0; i < p.length(); i++) {
pa[p.charAt(i) - 'a']++;
}
List<Integer> res = new LinkedList<>();
int left = 0;
for (int right = 0; right < s.length(); right++) {
sa[s.charAt(right)-'a']++;
if (right-left+1 < p.length()) {
continue;
} else {
if (isAnagram(sa, pa)) {
res.add(left);
}
sa[s.charAt(left)-'a']--;
left++;
}
}
return res;
}
private boolean isAnagram(int[] sa, int[] pa) {
for (int i = 0; i < SIZE; i++) {
if (sa[i] != pa[i]) {
return false;
}
}
return true;
}
}Example 1
Dictionary: "CDEBA"
Input: "ABC"
Output: "CBA"
string test(string& input, string& dictionary) {
int tmp[dictionary.length()];
std::fill(tmp, tmp+dictionary.length(), 0);
for (auto& c : input) {
size_t p = dictionary.find(c);
if (p != string::npos) {
tmp[p]++;
}
}
string result;
for (int i = 0; i < dictionary.length(); i++) {
while (tmp[i] > 0) {
result += dictionary[i];
tmp[i]--;
}
}
return result;
}Last updated
Was this helpful?