Leetcode: String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

spoilers alert... click to show requirements for atoi.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Analysis:
The crux of this question to handle all the cases for the input string, which include:

• Leading white spaces e.g. "   12" should be interpreted as 12
• Optional initial plus or minus sign "-5" should be -5, where "+5" should be 5
• The string starts by the optional sign and followed by all numerical digits until the non-digit character, and interprets them as a numerical value. The string can contain additional characters after that but will be ignored. For instance, " 3.1415926" will be interpreted as 3.
• Return 0 if
• The first sequence of non-whitespace characters in str is not a valid integral number
• The string is empty
• The string only contains whitespace characters
• Out of the range of representable values, return INT_MAX or INT_MIN

After we make clear all of those input cases, then we figure out how to handle each of them

• For leading white spaces, we can use Java trim() instance method of the String class to remove leading and trailing white spaces. Or we may use the static method isWhiteSpace(ch) in Character class to determine the white space and simply move the pointer until a non-whitespace character. 
• To handle optional initial plus or minus sign, there are several conditions to check
• For '+' character, use a flag to mark as plus. E.g. "+12" should be interpreted as 12
• For '-' character, mark the flag as minus
• For input if contains multiple signs, return 0. For e.g. "+++--4" return 0
• Then we check if the character next to the sign is a digit. If yes, we continue scan it until a non-digit character and save it to a temp string. Else, return 0. E.g. "-abc4" will return 0
• After that, we should get a string with only integers, e.g. "456". The next step is to convert the string into integers. We should also check the sign flag to get the number is positive or negative. 
• The next is to check if the integer is overflowed. This is pretty tricky, because we are unable to check the overflow after the string has been transformed into integers. One easy way is to use a long integer to save the transformed string. But how about the number is greater to the max value of long as well? We could check the length. If t he length of the string is greater than 9, the output will be either INT_MAX or INT_MIN. 

Code (Java):

public class Solution {
    public int atoi(String str) {
        boolean neg = false; // flag to mark if the converted integer positive or negative. 
        StringBuilder buf = new StringBuilder(); // temp buffer to store the converted string
        
        // check if the string is null or empty
        if (str == null || str.isEmpty()) return 0;
        
        // trim the leading whitespaces
        str = str.trim();
        
        // if string contains only whitespace characters
        if (str.isEmpty()) return 0;
        
        // get length of the trimed string
        int length = str.length();
        
        // Check if the first character of the string
        if (isNeg(str.charAt(0))) neg = true;
        else if (isPos(str.charAt(0))) neg = false;
        else if (Character.isDigit(str.charAt(0))) buf.append(str.charAt(0));
        else return 0;
        
        // check the first sequence of digit characters in the string
        int start = 1;
        while (start < length && Character.isDigit(str.charAt(start))) {
            buf.append(str.charAt(start));
            start++;
        }
        
        // check if the buf is empty
        if (buf.length() == 0) return 0;
        
        // check if the converted integer is overflowed
        long result;
        if (buf.length() <= 10) {
            result = toInteger(buf, neg);
        } else if (neg) {
            return Integer.MIN_VALUE;
        } else
            return Integer.MAX_VALUE;
            
        // Post-processing the convert long to int
        if (neg && result <= Integer.MAX_VALUE) {
            return 0 - (int) result;
        } else if (!neg && result <= Integer.MAX_VALUE) {
            return (int) result;
        } else if (neg && result > Integer.MAX_VALUE) {
            return Integer.MIN_VALUE;
        } else return Integer.MAX_VALUE;
    }
    
    private boolean isPos(char ch) {
        return ch == '+';
    }
    
    private boolean isNeg(char ch) {
        return ch == '-';
    }
    
    private long toInteger(StringBuilder buf, boolean neg) {
        int len = buf.length();
        long result = 0;
        for (int i = 0; i < len; i++) {
            result += Character.getNumericValue(buf.charAt(i)) * Math.pow(10, len - i - 1);
        }
        
        return result;
    }
}

Discussion:
The code looks ugly but handled all the input cases as far as I can think of. Specifically, it handles:

• Null or empty string
• Leading white spaces
• First character is sign 
• Leading character is non-sign nor digit
• First sequence of digit characters
• Calculate real integer number
• Handle overflow

Note that in the function toInteger() we convert a string with digital characters into an integer. 
For a specific character, how to convert to an integer? If the code above, I used an instance method getNumericValue(char ch). What if it is not allowed? Do we have a clever method? 

In all common character encodings, the values are sequential: '0' has a value one less than '1', which in turn followed by '2' and '3', which means:
'0' = ASCII_0;
'1' = 1 + ASCII_0;
'2' = 2 + ASCII_1;
 ... 
'9' = 9 + ASCII_9;
Therefore, to get a numeric value from a digital character, you just need to subtract from the '0'. For example, 9 = '9' - '0'. By this way you can avoid using getNumericValue(char ch) in your code. 

Secondly, to calculate the integer from a string we use  Math.pow() method. The idea is e.g. 123= 1 * 10^2 + 2 * 10^1 * 3 * 10^0. But power operation is usually quite costly in CPU cycles, so do we have a better idea without power function?

We still scan the string from left to right, but think about how 123 is calculated. When you see the first character , it will be 1. When you see the second character, it will be 1 x 10 + 2 = 12. When you see the first character , it will be 12 x 10 + 3 = 123. Now you must understand how to calculate a string from a string. 

Below is a new version of the Java code, besides the optimizations shown above, it does not need a temp buffer to store the digital string. On the contrary, it just calculated the integer once we got a digital character. 

public class Solution {
    public int atoi(String str) {
        boolean neg = false; // flag to mark if the converted integer positive or negative.
        
        // check if the string is null or empty
        if (str == null || str.isEmpty()) return 0;
        
        // trim the leading white spaces
        str = str.trim();
        
        // check if the string contains white spaces only
        if (str.isEmpty()) return 0;
        
        int i = 0;
        
        // check the sign position
        if (isNeg(str.charAt(0))) {
            neg = true;
            i++;
        } else if (isPos(str.charAt(0))) {
            neg = false;
            i++;
        }
        
        // calcuate the integer value of the digital string
        long result = 0;
        while (i < str.length() && i <= 11 && Character.isDigit(str.charAt(i))) {
            result *= 10;
            result += str.charAt(i) - '0';
            i++;
        }
        
        // check the sign flag
        if (neg) result = -result;
        
        // handle overflow
        if (result > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        if (result < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        
        return (int)result;
    }
    
    // check if the sign is negative
    private boolean isNeg(char ch) {
        return ch == '-';
    }
    
    // check if the sign is positive
    private boolean isPos(char ch) {
        return ch == '+';
    }
}

From Integer to String  
So far we learned how to convert from a string to integer. How about the reverse, i.e., convert from an integer to string? For example, given an integer 567, should be outputted a string "567". For integer -567, should be outputted as "-567". 

There are several things to consider: 
1. Convert an integer to string is easier because we don't need to consider the leading white spaces and overflow problems.. 
2. How to parse each digit from the integer. e.g. 567 should be parsed into 5 6 and 7. 
3. Given a digit value, how to convert to a corresponding character. 

For the second question, we can parse from either left to right or right to left. From left to right is easier but not very efficient. Now let's consider parse from right to left.  For the integer 732, we can do this way:

732 % 10 = 2
732 / 10 =  73

73 % 10 = 3
73 / 10 = 7

7 % 10 = 7 
7 / 10 = 0

So in this way we can find the digit 2, 3, 7 in a reversed order. We we have to use a temporary buffer to store the number reversely and put them into a string backward. 

For the third question, given an integer value, e.g. 7, how to get its character representation. Similar to the string to integer, we can add '0'. For instance, '7' = 7 + '0'. 

Below is the Java code:

public class IntToString {
  public static String intToString (int num) {
    boolean neg = false;

    if (num < 0) {
      neg = true;
      num = -num;
    }

    char buf[] = new char[11];
    
    int i = 0;
    do {
      buf[i++] = (char) (num % 10 + '0');
      num /= 10;
    } while (num != 0);

    StringBuilder result = new StringBuilder();

    if (neg) result.append('-');
    
    while (i > 0) {
      result.append(buf[--i]);
    }

    return result.toString();
  }
}

Summary:
In this post, we learned how to convert a string to an integer, and verse vera. 
Specifically, we learned:
1. How to get a digital value from the digital character? We used - '0'.
2. How to calculate the integer value from a string? We used "Horner's rule"
3. Howe to get a corresponding character from a digit? We used + '0'
4. How to get place value from an integer? We parsed the integer from right to left

Last but not least, this quest ion is not complicated. But the description of the question is intentionally vague. So it is very important to communicate with the interviewer to clarify the problem and ask as many questions as possible. 



Update on 10/14/14:

public class Solution {
    public int atoi(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        
        // Remove leading white spaces
        str = str.trim();
        
        char[] array = str.toCharArray();
        boolean neg = false;
        int i = 0;
        
        // Handle leading sign character
        if (str.charAt(i) == '-') {
            neg = true;
            i++;
        } else if (str.charAt(i) == '+') {
            i++;
        }
        
        // If leading character is not digital, return 0
        if (!isDigital(str.charAt(i))) {
            return 0;
        }
        
        // Find out the first sequence of digits
        ArrayList<Integer> digits = new ArrayList<Integer>();
        while (i < str.length()) {
            if (isDigital(str.charAt(i))) {
                digits.add(str.charAt(i) - '0');
                i++;
            } else {
                break;
            }
        }
        
        // Handle overflow
        if (digits.size() > 10 && neg == true) {
            return Integer.MIN_VALUE;
        } else if (digits.size() > 10 && neg == false) {
            return Integer.MAX_VALUE;
        }
        
        // Get results
        long result = 0;
        for (int j = 0; j < digits.size(); j++) {
            result = result * 10 + digits.get(j);
        }
        
        if (neg == true) {
            result = -result;
        }
        
        // Handle overflow
        if (result >= Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        } else if (result <= Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        } else {
            return (int) result;
        }
    }
    
    private boolean isDigital(char a) {
        return (a >= '0') && (a <= '9');
    }
}

Update on 9/29/15:

public class Solution {
    public int myAtoi(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        int i = 0;
        long result = 0;
        int n = s.length();

        // Step 1: skip the leading whitespaces, if any
        while (i < n && s.charAt(i) == ' ') {
            i++;
        }
        
        // Step 2: skip the '+' or '-' sign, if exists
        boolean isNeg = false;
        if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
            if (s.charAt(i) == '-') {
                isNeg = true;
            }
            i++;
        }
        
        // Step 3: parse the first sequence of numeric numbers
        int numDigits = 0;
        while (i < n && Character.isDigit(s.charAt(i))) {
            result = result * 10 + (s.charAt(i) - '0');
            i++;
            numDigits++;
        }
        
        if (numDigits > 10) {
            if (isNeg) {
                return Integer.MIN_VALUE;
            } else {
                return Integer.MAX_VALUE;
            }
        }
        
        if (isNeg) {
            result = -result;
        }
        
        if (result > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        
        if (result < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }
        
        return (int) result;
    }
}

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 Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Analysis:

1. What is a valid string?

We can list several examples to show the valid string:

• Empty string is always valid
• For string has only one pair of parentheses, (), [ ], { } are valid. However, (], {], (}, etc.. are not valid
• For string has two pairs of parentheses, ( )[ ], ([ ]), { }[ ] are valid. However, ( [ ) ], ( { } ] are not valid
• For string has  three pairs of parentheses, ( )[ ]{ }, { ( [ ] ) } are valid. However, { [ )} ( ] is not valid

Now we can use these examples to check if a string is valid. In addition, if the length of a given string is odd, it must be invalid. 

2. The problem presumes that the input string has just the characters of parentheses, square brackets, and brace. So we don't need to  consider other characters like white space, digit, etc... 

3. How to determine if a string is valid?

There are two conditions that a valid string must fulfill:

• The numbers of parentheses must match. For example, if there is a left parentheses, there must have a right one, so does for square brackets and brace. Therefore, the number of left parentheses must be equal to the right parentheses. 
• The brackets must be in the correct closing order. For example, { [ } ], although this string fuifills the first requirement, it is not the correct order. So how to determine the order is correct? Last-in-First-out. For instance, { ( ) } is valid because we see left brace first, we will see the right brace last. So you might already come out the idea! Yes, we can use a stack to store the parentheses. 
• Note that the problem does not require the order of the parentheses, i.e. { } should be outside of [ ], while [ ] must be outside of ( )

Solution:

According to the analysis, we can use the stack to solve this problem. 

• When we see a left parenthesis, (, [, or {, we push it into the stack. 
• When we see a right parenthesis, we pop the top element from the stack, and compare it with the right parentheses. If they are matched, check next character in the string; otherwise, directly returns the false. 
• If the stack is empty while the string has not reached the end, it must be the situation like ( ) ], then it returns the false.
• If the stack is not empty while the string has already reached the end, it must be the situation like ( ( ) then it returns the false. 

Now let's look at the implementation in Java.

Code (Java): 

public class Solution {
    public boolean isValid(String s) {
        final int length = s.length();
        if (length == 0) return true;
        if (length % 2 == 1) return false;
        
        Stack<Character> stack = new Stack<Character>();
        
        int index = 0;
        while (index < length) {
            char cur = s.charAt(index);
            if (isLeftBracket(cur)) {
                stack.push(cur);
                index++;
            }
            else if (isRightBracket(cur)) {
                if (stack.empty()) return false;
                char temp = stack.pop();
                if (!isPair(temp, cur)) return false;
                index++;
            }
        }
        return stack.empty();
    }
    
    // Determine the given parentheses is left
    private boolean isLeftBracket(char ch) {
        if (ch == '(' || ch == '[' || ch == '{') return true;
        else return false;
    }
    
    // Determine the given parentheses is right
    private boolean isRightBracket(char ch) {
        if (ch == ')' || ch == ']' || ch == '}') return true;
        else return false;
    }
    
    // Determine the left and right parentheses is a pair
    private boolean isPair(char left, char right) {
        if ((left == '(' && right == ')') || 
            (left == '[' && right == ']') || 
            (left == '{' && right == '}')
           )
         return true;
         else return false;
    }
}

Discussion:
Now we analyze the solution. Since we only iterate the input string only once, the time complexity is O(n). We need a stack to store the left parentheses. In the worst case the space is O(n). E.g. for the input string ( ( ( ( ( ( ( ( ( (. We just push the left parentheses into the stack until the end of the string. 


Summary:
In this problem we used the Java stack to have the parentheses pairing problem. Actually the stack is widely used in such kinds of pairing problem. Furthermore, you may notice that in the implementation, we used many modular programming paradigm, which is preferred in the code interview. We could firstly define the method and explain what does this mean, and implement it later. Sometimes you don't even need to implement those details. But this programming paradigm makes the coding looks neat. 

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;
    }
}

Leetcode: 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Analysis:
1. How to define the "closest" to the target? 
Given a target x, we could have an array of sum[] of each equals to the sum of three integers, so the closet is defined as distance = abs(sum[i] - target) and find the minimum distance. In this scenario, for the target x = 2, we can see that both 1 and 3 are closet to the target. 

2. The problem assumes that each input would have exactly one solution, so it is safe to return the value once we found. 
Follow-up:   What if there exists multiple solutions and required to return all triplets? 
We may store the results into an arrayList, which is similar to the 3sum problem. 

3. What is the return value? In this problem, what is returned is the sum of the triplet, of which is closest to the target. 

Naive Solution:
A native solution is to pick up each 3 elements from the array, and check the distance between its sum to the target. Use a hash table of which the key stores the distance, and value stores the sum of the triplet. At the end, we find the minimum distance in the hash table. Since the key in the hash table is always sorted, so the first pair is closest to the target. In this solution, finding the triplet takes O(n^3) time. Since the operations related to the hash table takes O(1) time, the overall time complexity is O(n^3). Since hash table needs additional O(n^3) space, the space complexity is O(n^3). In this problem, since we assume that there is exactly only one solution existed, one optimization is we return the sum if it equals to 0, i.e, the sum equals to the target. For the case that duplicated triplets exist, a key in the hash table may have two values. For instance, for the distance to 1 equals to 4, the sum could be either 5 or -3. In this case, we need a arrayList to store the value in the hash table. The implementation is omitted. We are aiming to look for a better solution.

A Better Solution:
Remember that in the 3sum problem we use two pointers to achieve the time complexity of O(n^2) and space O(1), can we borrow the idea to this problem? 

One thinking is do we really need a hash table to store distances and the corresponding sum? Note that we only need the minimum distance. Therefore, we only need to maintain a pair of minimal distance and its sum that we reduced the space complexity to constant. How about the time complexity? We could borrow the same idea in the 3sum. For a given array element num[i], use two pointers, start = i + 1 and end = length - 1. Then check the sum of num[i] + num[start] + num[end], and compute the distance to the target x, if it is equal to zero, immediately returns 0 and we're done. If the distance is less than zero, move the start and update the minimum pair, if the distance is larger than zero, move the end pointer and update the minimum pair. Following is the Java code:

Code (Java):

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        int length = num.length;
        Pair min = new Pair();
        
        // Sort the array
        Arrays.sort(num);
        
        for (int i = 0; i < length - 2; i++) {
            int start = i + 1;
            int end = length - 1;
            while (start < end) {
                int sum = num[i] + num[start] + num[end];
                int distance = sum - target;
              
                if (distance == 0) return sum;
                else if (distance < 0) start++;
                else end--;
                
                // update the pair
                if (Math.abs(distance) < min.first) {
                    min.first = Math.abs(distance);
                    min.second = sum;
                }
            }
        }
        
        return min.second;
    }
    
    private class Pair {
        private int first, second;
        
        private Pair() {
            first = Integer.MAX_VALUE; // store the distance
            second = 0; // store the sum
        }
    }
}

Discussion:
We can see that this implementation has the time complexity of O(n^2), and space complexity of O(1). Note that we created a private class called Pair to store the pair of <distance, value>, and the initial value of the distance is MAX integer. The purpose is to make the condition true for the first time.

Hash Table Solution:
Remember that in the 3sum problem we also proposed a hash table based solution, which has the time complexity of O(n^2) as well, but requires additional O(n) space to store the key-value pairs. Can we borrow the similar idea to this problem? Probably very hard. In the 3sum problem hash table works because the answer always "hits" the key in the hash table. However, in the 3sum closest problem, the answer might be not existed in the hash table, it is only "closet" to a key in the table. As a result, it is very to achieve O(1) time complexity in determining if a key is existed in the table.  

Summary:
In this question, we examined three ways in resolving the problem. During the code interview, it does not matter if you proposed a solution but finally found it does not work. But it is important that you analyze why it does not work and the possible work around.

Update on 7/12/18:

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int ans = nums[0] + nums[1] + nums[2];
        
        // Sort the array
        //
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length - 2; i++) {
            int newTarget = target - nums[i];
            
            int start = i + 1;
            int end = nums.length - 1;
            
            while (start < end) {
                // save the current result
                //
                int diff = Math.abs(nums[i] + nums[start] + nums[end] - target);
                
                if (diff < Math.abs(ans - target)) {
                    ans = nums[i] + nums[start] + nums[end];
                }
                
                if (nums[start] + nums[end] == newTarget) {
                    return target;
                } else if (nums[start] + nums[end] < newTarget) {
                    start++;
                } else {
                    end--;
                }
            }
        }
        
        return ans;
    }
}

Leetcode: 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

Understand the program:
This question is very similar to 3Sum and two-sum, as is we have discussed before. There are several requirements in the question:
1. Find all unique quadruplets in the array, so you cannot simply returns once you found a solution
2. Elements in a quadruplet(a,b,c,d) must be in non-descending order (a <= b <= c <= d)
3. The solution set must not contain duplicate quadruplets.
4. How to store the result: As is defined in the return value of the method, the quadruplet is stored in a ArrayList, and the result is stored in ArrayList of ArrayList. That is the basic data structure used in the problem.

Naive Solution:
Likewise the two sum and 3Sum problem, the native solution is very straight-forward. Pick up four elements from the array and check if the sum equals to the target. So it is obvious to know that the time complexity would be as large as O(n^4) in any case, as is required by the problem, we have to find all unique solutions. The Java implementation is omitted here.

A better Solution:
Now we consider the two pointer-based solution. We consider this solution first because it has the same time complexity as the hash table solution, but requires no additional space to store the key-value pairs as is in the hash table. 

Noted that the the problem wanna find a + b + c + d = target? It equals to a + b = target - (c + d)? So the basic idea is given a pair (a, b), we aim to find that if there is another pair (c, d) and the target - its sum equals to the sum of (a ,b). Simply, for target is zero, we aim to find a pair (c ,d) of which the sum equals to the negative sum of (a, b). The trick is to sort the array first, so given a pair (a, b), use two pointers start from the end of the array and right-hand side of the b. 

There is still another question: How do you handle duplicated quadruplets.
E.g. for the input array[-2, -1, -1, 0, 0, 2, 2, 2]. As you've already seen before, the duplicated elements in the array will be placed together due to the sorting.  Here is the idea: if you have seen the number before, you don't need to check it again, just simply jump to next until one is not duplicated. Here is the Java code:

Code (Java):

public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        final int length = num.length;
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        
        if (length < 4) return result;
        
        // Sort the array
        Arrays.sort(num);
        
        for (int i = 0; i < length - 3; i++) {
            if (num[i] > target) break;
            if (i == 0 || num[i] > num[i - 1]) {
                for (int j = i + 1; j < length - 2; j++) {
                    if (j == i + 1 || num[j] > num[j - 1]) {
                        if ((num[i] + num[j]) > target) break;
                        int start = j + 1;
                        int end = length - 1;
                        int newTarget = target - (num[i] + num[j]);
                        while (start < end) {
                            if ((num[start] + num[end]) == newTarget) {
                                ArrayList<Integer> temp = new ArrayList<Integer>(4);
                                temp.add(num[i]);
                                temp.add(num[j]);
                                temp.add(num[start]);
                                temp.add(num[end]);
                            
                                result.add(temp);
                                start++;
                                end--;
                                while (start < end && num[start] == num[start - 1]) start++;
                                while (start < end && num[end] == num[end + 1]) end--;
                            } else if (num[start] + num[end] < newTarget) {  
                                start++;
                            } else {
                                end--;
                            }
                        }
                    }
                }
            }
        }
        return result;
    }
}

Look the code carefully then you will find a bug. Let's see the results first. According to the OJ, it failed the test:

Input:	[1,-2,-5,-4,-3,3,3,5], -11
Output:	[]
Expected:	[[-5,-4,-3,1]]

But why? According to the code above, we sorted the array first, so it becomes [-5, -4, -3, -2, 1, 3, 3, 5], and the target is -11. 
Now you might find the problem. In Line 11, it checks 

if (num[i] > target) break;

However, when the target is a negative number , this condition no longer stands, because as is shown in the data input above, even if num[i] is greater than the target, it is possible that the numbers on the right hand side of num[i] are negative number. So we still have to check. 
For the case when the target is equal or greater than 0, this condition stands anyway, because the num[i] and its later on numbers must be positive numbers. Consequently, after we removed the line 12 and 16, the code becomes correct, which is as shown below:

public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        final int length = num.length;
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        
        if (length < 4) return result;
        
        // Sort the array
        Arrays.sort(num);
        
        for (int i = 0; i < length - 3; i++) {
            if (num[i] > target) break;
            //if (i == 0 || num[i] > num[i - 1]) {
                for (int j = i + 1; j < length - 2; j++) {
                    //if (j == i + 1 || num[j] > num[j - 1]) {
                        if ((num[i] + num[j]) > target) break;
                        int start = j + 1;
                        int end = length - 1;
                        int newTarget = target - (num[i] + num[j]);
                        while (start < end) {
                            if ((num[start] + num[end]) == newTarget) {
                                ArrayList<Integer> temp = new ArrayList<Integer>(4);
                                temp.add(num[i]);
                                temp.add(num[j]);
                                temp.add(num[start]);
                                temp.add(num[end]);
                            
                                result.add(temp);
                                start++;
                                end--;
                                while (start < end && num[start] == num[start - 1]) start++;
                                while (start < end && num[end] == num[end + 1]) end--;
                            } else if (num[start] + num[end] < newTarget) {  
                                start++;
                            } else {
                                end--;
                            }
                        }
                    //}
                }
            //}
        }
        return result;
    }
}

Discussion:
In this solution, sorting the array takes O(nlogn) time, and the nested loop takes O(n^3) time, so the total time complexity is bounded by O(n^3). Since we don't take additional storage in this solution, the space complexity is O(1). 

HashMap Solution:
Here I also introduced the hashMap solution, its time complexity is still O(n^3), but takes additional O(n^3) space to store the key-value pairs, which is not desirable when the storage space is constraint.

public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        HashMap>Integer, ArrayList>Integer>> hashMap = new HashMap<Integer, ArrayList<Integer>>();
        HashSet<ArrayList<Integer>> hashSet = new HashSet<ArrayList<Integer>>();
        
        final int length = num.length;
        if (length < 4) return result;
        
        Arrays.sort(num);
        
        for (int i = 0; i < length - 3; i++) {
            for (int j = i + 1; j < length - 2; j++) {
                hashMap.clear();
                for (int k = j + 1; k < length; k++) {
                    if (hashMap.containsKey(num[k])) {
                        ArrayList<Integer> temp = new ArrayList<Integer>(4);
                        temp.add(0, hashMap.get(num[k]).get(0));
                        temp.add(1, hashMap.get(num[k]).get(1));
                        temp.add(2, hashMap.get(num[k]).get(2));
                        temp.add(3, num[k]);
                        
                        // Remove duplicated keys
                        if (!hashSet.contains(temp)) {
                            result.add(temp);
                            hashSet.add(temp);
                        }
                    } else {
                        ArrayList<Integer> tmp = new ArrayList<Integer>(3);
                        tmp.add(0, num[i]);
                        tmp.add(1, num[j]);
                        tmp.add(2, num[k]);
                        int key = target - (num[i] + num[j] + num[k]);
                        hashMap.put(key, tmp);
                    }
                }
            }
        }
        return result;
    }
}

  
Note that the code above used Java hashSet. Its purpose is to check the duplicated key in the final result list. If not contains, we add the quadruplet into both the result list and the hashSet. Since get elements from hashSet requires O(1) time complexity, it will not complicate the overall implementation, but makes the code looks neat. However, it is at the cost of additional space to store the final result. Also please note that since we clear the hashMap before each inner loop, therefore, the hashMap at most stores the number of n - 2 key-value pairs, which at the cost of O(n). 

In this solution, we used the Java HashSet, what the difference between HashMap and HashSet? The difference is actually obvious:
In a HashMap, you store the key-value pair;
In a HashSet, you store only keys.

The Java HashSet has the following common instant methods:

• boolean add(E e) -- Add the specified element, e, into the set if it is not present and return the true. If the set has already contains the element, the call leaves the set unchanged and returns false. Note it is very different from HashMap put(Key key, Value value), where if the map contains the key to be added, it will simply override the key with the updated value. 
• void clear() -- Clear all elements of the set
• boolean contains(Object o)  -- returns true if the set contains the specified element
• boolean remove(Ojbect o) -- remove the specified element o, returns true if the list contains that element. If the set does not contain that element, returns false.
• int size() -- returns the number of the elements in the set

Summary:
So far we have seen the k-sum problems, where the k equals to 2, 3 or 4. To summarize, we might observe that the k-sum problem could have the time complexity ofO(n^(k-1)). 
And the bast space complexity is O(1). 

Last but not least, the big lesson we learned from this post is it is very important to make every single line of code count. It is not a good idea to rush and write the code. You need to analyze the requirements of the problem very clearly at first before you implement your code. You should also make sure every single line in the code makes sense. That is very important to write bug-free code. Another tip for Leetcode OJ is whenever you finish your code, don't rush to submit your code, you should go through your code and use several test cases to check if there is any bug. In a real code interview, there is no such an online compiler which can help debugging. So make your best to submit only bug-free code to OJ.