Leetcode: 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"]
]

Clarify the problem:
1. What is a palindrome?
In our previous post, we defined the palindrome as given a "A word, phrase, number, or other sequences of symbols or elements that reads the same forward or reversed, with general allowance for adjustments to punctuation and word dividers. " 

In this question, do we allow the input string contains white space, punctuation and word dividers? Do we ignore cases? E.g. Does string "Aa" a palindrome? Actually the question does not specify this, so is in the real interview. So it is very important to clarify this with the interviewer. It is an important step to show you really think about the problem. In this problem, we may assume that the input string has no punctuation, and all alphabets are lower cases. In real word, people usually ignore the cases and punctuation. For example, the link provides a list of palindrome. http://www.palindromelist.net/ 
From that, it is obviously to see that palindrome usually ignores cases and punctuation. Therefore, in this question, we shall do a pre-process that removes all punctuation and converts all upper cases characters to lower cases.  

2. What is a substring in a string?
A substring could be either the string itself or its substrings. For instance, for string "run", its sbustring could be: 
r
u
n
ru
un
run

3. What is a partition of a string?
A partition of a string is to partition a string into its substrings. For instance, the partition of a string "run" will be
run
ru, n
r, un
r, u, n

4. What is the basic data structure used in this problem?
The next question is how to store the substrings which are palindrome? We could simply use a ArrayList, of each element stores the substring which is a palindrome for the specified string. For example, for the string "aab", we returns 
["aa", "b"] and ["a", "a", "b"]

Naive Solution:
According to the analysis above, now you may get the basic idea of the solution. We could find all partitions of the string and check if it is palindrom. For instance, for the string "aab" we first check is the first partition "aab" a palindrome? Obviously it is not. So we keep searching its sub-partitioning. If we only partition once, the partition of the string "aab" could be "aa", "b" or "a", "ab". For a given partition, we check if every substring of the partition is a palindrome. If yes, we store the substrings into a ArrayList. 

So the native solution has two steps.  We first find all partitions of a given string, then we check every substring in a partition is a palindrome. 

Recursive Solution:

public class Solution {
    public ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
        ArrayList<String> levelList = new ArrayList<String>();
        
        partitionHelper(s, result, levelList);
        
        return result;
    }
    
    private void partitionHelper(String s, ArrayList<ArrayList<String>> result, ArrayList<String> levelList) {
        if (s.isEmpty()) {
            result.add(new ArrayList<String>(levelList));
            //levelList.clear();
            return;
        }
        
        for (int i = 1; i <= s.length(); i++) {
            if (isPalin(s.substring(0, i))) {
                levelList.add(s.substring(0, i));
                partitionHelper(s.substring(i), result, levelList);
                levelList.remove(levelList.size() - 1);
            }
        }
    }
    
    private boolean isPalin(String s) {
        if (s.isEmpty()) return true;
        
        int len = s.length();
        int start = 0;
        int end = len - 1;
        
        while (start < len) {
            if (s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            } else {
                return false;
            }
        }
        return true;
    }
}

Discussion:
Note that in line 14 and 22, which are the most tricky parts in the code. 

Summary:
The problem is tricky however not too hard. Do understand the ideas of partitioning the string. It is commonly used in many other string partitioning problem.

Update on 10/28/14:

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<List<String>>();
        if (s == null || s.length() == 0) {
            return result;
        }
        List<String> curr = new ArrayList<String>();
        partitionHelper(0, s, curr, result);
        
        return result;
    }
    
    private void partitionHelper(int start, String s, List<String> curr, List<List<String>> result) {
        if (start >= s.length()) {
            result.add(new ArrayList<String>(curr));
            return;
        }
        
        for (int i = start; i < s.length(); i++) {
            if (isPalin(start, i, s)) {
                curr.add(s.substring(start, i + 1));
                partitionHelper(i + 1, s, curr, result);
                curr.remove(curr.size() - 1);
            }
        }
    }
    
    private boolean isPalin(int start, int end, String str) {
        while (start < end) {
            if (str.charAt(start) != str.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}  

Leetcode: Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Analysis:

1. What is a palindrome?

According to wiki, a palindrome is "A word, phrase, number, or other sequences of symbols or elements that reads the same forward or reversed, with general allowance for adjustments to punctuation and word dividers. " 

2. What is the allowance for adjustments to punctuation in this question?

We only need to consider the alphanumeric characters, thus ignoring space, comma, colon, etc. Note that we also ignore cases in this question. So A equals to a.

3. Come up one or two examples to show the problem?

First, is an empty string a palindrome? Yes, at least for this question.

Second, is a string with only one character a palindrome? Yes, since it reads the same with forward and backward.

Third, the example showing above is a palindrome.

Naive Solution:

How to determine if a given string is a palindrome? Remember the definition of the palindrome. A string reads the same forward and backward is a palindrome. Consequently, a brute force solution is to read the string backward from the end, store it into a temp string, and then compare each character of the original string and the temp string. It should be the same if the original string is a palindrome. How complex of this solution is? We need to read the string twice, one to reverse the string, one to compare with the original string. So the total cost is O(n) + O(n) = O(n). Since it needs an additional string to store the reversed string, the space complexity is O(n) as well.  Do we have a better solution? The answer is yes.

A Better Solution:

Remember the definition of the palindrome: a string should be read the same forward and backward. As a result, every single character should be the same if we read from start and end. Now you may get the idea. We maintain two pointers, one iterate from start of the string, one from end of the string and iterate the string in a reversed order. We move the two pointers at the same time until we have checked all characters in the string. How abut the complexity of this solution? Since we only iterate the string at most once, the worst case complexity is O(n). In this solution, we don't need to allocate temp buffers to store the reversed string, so it is in-place check and the space complexity is O(1). 

For the Java implementation, how to get a char at a given index, we use charAt(int index) instant method. Note that we only consider alphanumeric characters and ignore cases. 

First of all, how to check if character is alphanumeric? To check if a character is alphabet or number, we use instance method of Class Character 

static boolean isLetter(char ch)

static boolean isDigit(char ch)

Note that they are static methods, so calling the method should be like:

Character.isLetter(ch)

else it is impossible for the compiler to know the instance method isLetter() belongs to which Class. 

To handle the lower case and upper case issue, use two instance methods from the Character class

static boolean isLowerCase(char ch)

static boolean isUpperCase(char ch)

Use these two instance methods to convert any upper case characters into lower case. Also note that they are also static methods, so calling the method should be:

Character.isLowerCase(ch);

Code (Java):

public class Solution {
    public boolean isPalindrome(String s) {
        int length = s.length();
        if (length == 0 || length == 1) return true;
        
        int start  = 0;
        int end = length - 1;
        
        while (start < end) {
            // determine if the char is an alphanumeric
            while ((start < end) && (!isAlphaNum(s.charAt(start)))) start++;
            while ((start < end) && (!isAlphaNum(s.charAt(end)))) end--;
            
            // check if lower case
            Character lStart = s.charAt(start);
            Character lEnd = s.charAt(end);
            if (!Character.isLowerCase(lStart)) lStart = Character.toLowerCase(lStart);
            if (!Character.isLowerCase(lEnd)) lEnd = Character.toLowerCase(lEnd);
            
            if (lStart.equals(lEnd)) {
                start++;
                end--;
            } else {
                return false;
            }
        }
        return true;
    }
    
    private boolean isAlphaNum(char ch) {
        return (Character.isLetter(ch) || Character.isDigit(ch)) ? true : false;
    }
}

Discussion:

If using the instance methods such as isLetter(char) or isDigit(char) is not allowed, we can simply implement it manually. For example, isLetter(char ch) can be implemented as:

private boolean isLetter(char ch) {
    if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
        return true;
    else
        return false;
}

Another Interesting Solution:

I found there is another very interesting solution posted here:

http://www.programcreek.com/2013/01/leetcode-valid-palindrome-java/

In this solution, we first removed the non-alphanumeric characters from the array and convert all characters to lower cases. After that, we get a very neat string with only lower case characters. Then we employ a stack, and push the first half of the string into the stack, then pop and compare with the second half of the string. The code is as below:

Code (Java):

public class Solution {
    public boolean isPalindrome(String s) {
        int length = s.length();
        if (length < 2) return true;
        
        // Replace the non-alphanumeric characters first
        String delim = "[^a-zA-Z0-9]";
        s = s.replaceAll(delim, "").toLowerCase();
        
        length = s.length();
        if (length < 2) return true;
        
        Stack<character> stack = new Stack<character>();
        
        int index;
        for (index = 0; index < length/2; index++) {
            stack.push(s.charAt(index));
        }
        
        // Handle if the length of string is odd
        if (length % 2 == 1) index++;
        
        while (index < length) {
            char temp = stack.pop();
            if (temp != s.charAt(index)) return false;
            else index++;
        }
        return true;
    }
}

The implementation is very straight-forward but tricky. The only thing needs to take care is if the length of the trimmed string is odd, we need to jump the "middle" character in the string. The advantage of the implementation is it iterates the string only from forward order. This is an useful property when the input is a singly linked list, where we can only iterate the list from beginning. The disadvantage of this solution is it needs O(n/2) additional space to store the stack elements. In addition, since string is immutable, the replaceAll() method actually allocates a new string which takes additional O(n) space at the worst case.

Summary

In this question, we used two methods to determine if a string is a palindrome: use two pointers or stack. Last but not least, we can clearly see that for writing neat and efficient Java programs, it is important to be familiar with commonly used Java instance methods. So please memorize as many as you can.   

Update on 4/14/19:

public class Solution {
    /**
     * @param s: A string
     * @return: Whether the string is a valid palindrome
     */
    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 && !Character.isLetterOrDigit(s.charAt(start))) {
                start++;
            }
            
            while (start < end && !Character.isLetterOrDigit(s.charAt(end))) {
                end--;
            }
            
            char startChar = Character.toLowerCase(s.charAt(start));
            char endChar = Character.toLowerCase(s.charAt(end));
            
            if (startChar != endChar) {
                return false;
            }
            
            start++;
            end--;
        }
        
        return true;
    }
}