Palindrome related

Leave a comment

September 5, 2016 by oneOokay

***斗胆开一个Palindrome的合集***╯-_-)╯ ~╩╩

Palindrome:回文,回文串


266. Palindrom Permutation

Given a string, determine if a permutation of the string could form a palindrome.

For example,
"code" -> False, "aab" -> True, "carerac" -> True.


Easy级别:主要是掌握一下两种方法:计数法(array)和不计数法(set)

  1. 用int[256]对整个string进行计数,如果出现多过一个的出现奇数次数的char,说明不是Palindrome
  2. 用set:遍历整个string,如果存在char,把它从set里面移除;如果不存在char,加入set。最终如果set.size()<=1的话,为palindrome;否则不是。

409. 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.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

同样的有计数(array)和set的方法:

计数:注意:如果是奇数,那么总count要加上这个奇数-1;最后存在奇数的话再+1

set:计算pair的数量,最终count为pair的数量X2,如果set size大于1的话再+1.


415. Valid Palindrome: 用头尾指针的方法从两端往内移,进行判断。

这题超容易有bug:主要是它只考虑字母和数字且忽略大小写,其他的符号和空格不计。

记住几个method吧: Character.toLowerCase(); Charactor.isLetter(); Charactor.isDigit(). s.length(), s.charAt()

public class Solution {
public boolean isPalindrome(String s) {
if (s == null || s.length() == 0){
return true;
}
int start = 0;
int end = s.length() – 1;
while (start < end) {
while (start < end && !isValid(s.charAt(start))){
start ++;
}
while (start < end && !isValid(s.charAt(end))){
end –;
}
if (Character.toLowerCase(s.charAt(start)) != Character.toLowerCase(s.charAt(end))){
return false;
}
start ++;
end –;
}
return true;
}

private boolean isValid(char c){
return Character.isLetter(c) || Character.isDigit(c);
}
}

136. 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.

DFS遍历 + back trace求解,这里主要想好哪个是定着不变的,哪个是按i增加的。

  • 从index为0开始,以i为长度切割string (s.substring(startIndex, endIndex)),startIndex不变,endIndex逐渐变大,直到切完或者找到solution。
  • 切完一个之后index + 1再切下一个直到index == s.length().
  • string.substring(startIndex[inclusive], endIndex[exclusive])

public class Solution {
public List partition(String s) {
List result = new ArrayList();
if (s == null || s.length() == 0) {
return result;
}

ArrayList path = new ArrayList();
helper(s, 0, path, result);
return result;
}

private void helper(String s, int start, ArrayList path, List result){
if (start == s.length()){ //因为helper那是i + 1,所以这里会是s.length()而不是s.length() – 1
result.add(new ArrayList(path));
return;
}

for (int i = start; i < s.length(); i ++){
String prefix = s.substring(start, i + 1); //因为起始状态是i = start,start = 0,所以这里要i + 1保证最小切一个char。 切割出该部分之后来判断它是否是palindrome
if (!isPalindrome(prefix)){
continue; //若不是,i ++ ,start起点不变,切割的endIndex增大
}

path.add(prefix);
helper(s, i + 1, path, result);//s.substring 的endIndex是i + 1(exclusive), 所以下一个切割的startIndex为i + 1(inclusive)
path.remove(path.size() – 1);
}
}

private boolean isPalindrome(String s) {
int start = 0;
int end = s.length() – 1;
while (start < end) {
if (s.charAt(start) != s.charAt(end)){
return false;
}
start ++;
end –;
}
return true;
}
}

223. Palindrome LinkedList

Implement a function to check if a linked list is a palindrome.

快慢指针找到linkedList的中点,分成两段,reverse后面一段,再从头和中点两指针开始同时走进行判断。

这里也要注意中点:当总node为偶数的时候,slow会停在前一段的最后一个;当总node为奇数的时候,slow会停在正中间。所以

  • slow.next永远是下一段的第一个点.
  • 快慢指针分成的两段的长度的关系是: 前段长度==后段长度或者前段长度==后段长度+1.

快慢指针找到中点和reverse linkedlist要背下来啊=。=

public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
ListNode middle = findMiddleNode(head);
ListNode p1 = head;
ListNode p2 = reverse(middle.next);
while (p1 != null && p2 != null && p1.val == p2.val){
p1 = p1.next;
p2 = p2.next;
}
return p2 == null; 
//这里必须是p2. 当这个linked list总node数为单数的时候,p1的数目是p2+1
循环结束如果是Palindrome,p2必定为null;如果不是Palindrome,那么p2(和p1)会
一起停在不同的那个位置。
}
private ListNode findMiddleNode(ListNode head) {
//利用快慢指针来找到中点。
如果linkedlist的node数目为单数的时候,slow会停在正中间的位置;
当linkedlist数目为双的时候,会有两个元素处于正中间,slow会停在第一个的中间位置。
if (head == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
//这一段也要能闭着眼睛写出来啊。
private ListNode reverse(ListNode head){
ListNode prev = null;
while (head != null) {
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: