1/27，Palindrome
Valid Palindrome
string two pointer类的问题，两指针对撞型，用迭代排除掉左右两边都不考虑的字符。注意：considering only alphanumeric characters and ignoring cases.
class Solution {
public boolean isPalindrome(String s) {
if (s == null || s.length() == 0) return true;
char[] arr = s.toCharArray();
int n = arr.length;
int i = 0, j = n - 1;
while (i < j) {
while (i < j && !Character.isLetterOrDigit(arr[i])) i++;
while (i < j && !Character.isLetterOrDigit(arr[j])) j--;
if (i < j) {
char left = Character.toLowerCase(arr[i]);
char right = Character.toLowerCase(arr[j]);
if (left != right) {
return false;
}
i++;
j--;
}
}
return true;
}
}
再遇到这道题一定要再做之前make sure前提，是不是case sensitive，是不是只用考虑数字和字母等。
1/12复习注，a lot of questions to ask, e.g. is an empty string a valid palindrome? what constitute a string? case sensitive?
inner while loop的作用就是找到要比较的chars。
2/10补充，
如何上一题我们只是判断一个string或者array是不是palindrome，可以O(n) time，O(n^2) extra space (array slicing + recursive function calls) 但是，如果n很长，在这道题用这个recursive会stack overflow
class Solution {
public boolean isPalindrome(String s) {
return isCheck(s.toCharArray(), 0, s.length() - 1);
}
private boolean isCheck(char[] arr, int start, int end) {
if (start > end - 1) {
return true;
}
while (start < end && !Character.isLetterOrDigit(arr[start])) start++;
while (start < end && !Character.isLetterOrDigit(arr[end])) end--;
if (start >= end) return true;
return Character.toLowerCase(arr[start]) == Character.toLowerCase(arr[end])
&& isCheck(arr, start + 1, end - 1);
}
}
Valid Palindrome 2
好题，用greedy的方法来做，从两边开始check，如果valid直接返回true，otherwise，check左删除一个或者右删除一个character能否valid。
time: O(n) each of two checks of whether some substring is a palindrome is O(N)
space: O(1) only pointers are stored in memory.
class Solution {
public boolean isPalindromeRange(String s, int i, int j) {
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
i++;
j--;
} return true;
}
public boolean validPalindrome(String s) {
if (s == null || s.length() == 0) return true;
for (int i = 0; i < s.length() / 2; i++) {
int left = i, right = s.length() - 1 - i;
if (s.charAt(left) != s.charAt(right)) {
return (isPalindromeRange(s, left + 1, right) ||
isPalindromeRange(s, left, right - 1));
}
} return true;
}
}
Longest Palindromic Substring
并不难，关键是要想到palindrome的长度可能是奇数，可能是偶数，怎么能充分检查所有情况。做法是在string的每个位置，用two pointers反向check palindrome，由于存在奇偶性，同一个位置检查两遍才行。在two pointers向两边移动的同时，update最长的长度，储存左右边界。时间复杂度O(n^2)。注意，设置max和lo为全局变量，这样设计会使代码更加简洁。
class Solution {
int max = 0;
int lo = 0;
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) return "";
for (int i = 0; i < s.length(); ++i) {
getPalindrome(s, i, i);
getPalindrome(s, i, i + 1);
}
return s.substring(lo, lo + max);
}
private void getPalindrome(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
// check the length after the while loop
if (max < right - left - 1) {
max = right - left - 1;
lo = left + 1;
}
}
}
1/12，总结一些简单的关于Longest题目。
- 一个共同点是在迭代过程中使用变量保存max length。
Longest palindrome substring和Longest substring without repeating chars比较，都用到two pointer。
Longest common prefix高频题。
Longest consecutive sequence使用hash set解决。
Palindrome Permutation
检查一个字符串是否是permutation of a palindrome。利用hashtable，第一次遍历统计次数，第二次遍历检查次数是奇数的个数。
这种方法只检查了字母，如果中间有whitespace要如何处理需要check，是当作一个独立的letter还是直接ignore。
class Solution {
public boolean canPermutePalindrome(String s) {
if (s == null || s.length() == 0) return true;
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
map.put(c, map.getOrDefault(c, 0) + 1);
}
int odd = 0;
for (char key : map.keySet()) {
if (map.get(key) % 2 == 1) {
odd++;
}
}
return odd <= 1;
}
}
Palindrome Permutation 2
Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
运用上一题的idea，来一个略暴力的构建string。Basic idea is that 首先找到中间center点，在过程中如何发现构成不了valid的Palindromes，直接返回空list。在构建Palindromes过程中，从center位置向两边extend。time O(n!), space O(n)
the idea is to build a count map for the chars in s // and terminate if s cannot form a palindrome // then do DFS from the center until reaching the left/right end
class Solution {
public List<String> generatePalindromes(String s) {
if (s == null || s.length() == 0) return new ArrayList<String>();
int[] hash = new int[256];
for (int i = 0; i < s.length(); ++i) {
int index = (int)s.charAt(i);
hash[index]++;
}
char center = '.';
boolean oneOdd = false;
for (int i = 0; i < 256; ++i) {
if (hash[i] % 2 == 0) {
continue;
} else {
if (oneOdd) return new ArrayList<String>();
oneOdd = true;
center = (char) i;
hash[i]--;
}
}
char[] array = new char[s.length()];
List<String> list = new ArrayList<>();
if (oneOdd) {
array[s.length() / 2] = center;
dfs(list, array, hash, s.length() / 2 - 1, s.length() / 2 + 1);
} else {
dfs(list, array, hash, s.length() / 2 - 1, s.length() / 2);
}
return list;
}
private void dfs(List<String> list, char[] array, int[] hash, int left, int right) {
if (left < 0 || right >= array.length) {
list.add(new String(array));
return;
}
for (int i = 0; i < 256; ++i) {
if (hash[i] <= 0) continue;
array[left] = (char) i;
array[right] = (char) i;
hash[i] -= 2;
dfs(list, array, hash, left - 1, right + 1);
hash[i] += 2;
array[left] = '.';
array[right] = '.';
}
}
}
Longest Palindrome
Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
This is case sensitive, for example
"Aa"is not considered a palindrome here.Given s =
"abccccdd"return7One longest palindrome that can be built is
"dccaccd", whose length is7
字符串中的字母可以随便使用。palindrome可能的构成方式有两种，一种是全部是偶数次的字符，另一种是偶数次的字符和一个奇数次的字符(如果有)。所以问题的关键是找出所有出现了奇数次的字符的个数。最后，最大长度等于总长度减去(奇数次字符的个数-1)。
class Solution:
def longestPalindrome(self, s):
odd_num = {}
for char in s:
if char in odd_num:
del odd_num[char] ## pay attention，当一个出现了两次时，就删掉
else:
odd_num[char] = True
remove = len(odd_num)
if remove > 0:
remove -= 1
return len(s) - remove
shortest palindrome
标注为hard，实际上这个题有两种解法，第一种解法是O(n^2), 第二种解法是KMP，O(n),
Let's first see the basic logic of this question. Given a string, out aim is to add a string in the front to make the new string a palindrome. Say the given string is S, the string we add in the front is denoted as P, so the result string is PS, which needs to be a palindrome. According to the definition of palindrome, we can rewrite string PS into:
PS = PQP' where QP' = S and P' is the reverse of string P
So, if we want P as short as possible, in other words, we want Q as long as possible. Then the original problem can be converted into the problem that find the largest palindrome starting with the first character.
First method, using two pointer, time: O(n ^ 2) worst case: aaaaaabcaaaaaa
class Solution {
public String shortestPalindrome(String s) {
if (s == null || s.length() <= 1) return s;
int i = 0;
int end = s.length() - 1;
int j = end;
while (i < j) {
if (s.charAt(i) == s.charAt(j)) {
i++;
j--;
} else {
i = 0;
end--;
j = end;
}
}
return new StringBuilder(s.substring(end + 1)).reverse().toString() + s;
}
}
Second method, using KMP, refer: http://yucoding.blogspot.com/2015/10/leetcode-question-shortest-palindrome.html
Time: O(n) space: O(n)