Leetcode–Validate Binary Search Tree

The Problem:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Notes:

  1. Note that a valid BST should have ALL node in the left less than the root (of each level), not only the immediate left child. This impose a min-max constraint of all the nodes other than top root.
  2. In the recursion, it also pass that min-max constraint from top to bottom. In each recursion it checks left and right node not only valid for their parent (left < root < right), but also check if they are in the min-max range (The range is built up by all their ancestors).

Java Solution

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   public boolean isValidBST(TreeNode root){
        return isValid(root Integer.MIN_VALUE, Integer.MAX_VALUE) ;
    }
 
    private boolean isValid(TreeNode root, int min, int max){
        if(root==null) return true;
        if(root.val <= min || root.val >= max)
            return false;
        return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
    }
}
Advertisements

Leetcode–Valid Palindrome

The Problem:

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.

Notes:

  1. Ignore cases: convert all to lowercase
  2. Only alphanumeric: first I wrote a function to check each char if is alphanumeric. Then another way to handle it is to use regular expression replace all non-alphanumeric char with “”

Java Solution

public class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        s = s.replaceAll("[^A-Za-z0-9]", "");
        if(s.length()== 0)return true;
        for(int i = 0, j = s.length()-1; i<=j; i++, j-- ){
            if(s.charAt(i) != s.charAt(j))
                return false;
        }
        return true;
    }
}

Leetcode–Valid Number

The Problem:

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Notes:

  1. The problem is ambigous and need to clarify a lot of special cases before implementing. Some cases I found in test cases that are not that intuitive are:
    1. 01 ->true
      e9->false
      3. ->true
      .1 -> true
      46.e3-> true
  2. Notice that for ‘e’ and ‘.’ can only appear once. And all special non-digit characters has rules for the character following. When using flag to mark its immediate follower, need to reset all the flags in all the branches.

Java Solution

public class Solution {

    public boolean isNumber(String s) {
        s = s.trim();
        if(s.length()==0) return false;
        boolean foloDot = false;
        boolean hasExpo = false;
        boolean foloE = false;
        boolean hasDot = false;
        boolean hasSign = false;
        boolean foloSign = false;
        boolean hasNum = false;
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch=='e'){
                if(!hasNum ||hasExpo || foloSign ||  i==s.length()-1)
                    return false;
                hasExpo = true;
                foloE = true;
                foloDot = false;
                foloSign = false;
            }
            else if(ch=='.'){
                if((!hasNum&&i==s.length()-1)  || hasDot || hasExpo )
                    return false;
                hasDot = true;
                foloDot = true;
                foloE = false;
                foloSign = false;
            }
            else if(ch=='+' || ch=='-'){
                if((hasSign && !foloE)|| i==s.length()-1 || (hasNum && !foloE) || foloDot)
                    return false;
                hasSign = true;
                foloSign = true;
                foloDot = false;
                foloE = false;
            }
            else if(ch>='0' && ch <='9'){
                foloDot = false;
                foloE = false;
                foloSign = false;
                hasNum = true;
            }
            else
                return false;
        }
        return true;
    }
}

Leetcode–Set Matrix Zeroes

The Problem:

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

 

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Notes:

  1. A simple O(m+n) solution is to record the row/column needs to reset. If we are strict on the space, one way to do it is to reuse the matrix itself. For example we can use the first row to record the columns needs to reset, and only need one other flag to tell if the first row itself needs reset.

Java Solution

public class Solution {
    public void setZeroes(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        if(n==0 || m==0) return;
        boolean row0 = false;
        for(int j = 0; j < m; j++){
            if(matrix[0][j]==0){
                row0 = true;
            }
        }
        for(int i = 1; i < n; i++ ){
            boolean hasZero = false;
            for(int j = 0; j < m; j++){
                if(matrix[i][j]==0){
                    matrix[0][j]= 0;
                    hasZero = true;
                }
            }
            if(hasZero){
                for(int j = 0; j < m; j++){
                    matrix[i][j] = 0;
                }
            }
        }
        for(int j = 0; j < m ; j++){
            if(matrix[0][j] == 0){
                for(int i = 1; i < n; i++){
                    matrix[i][j] = 0;
                }
            }
        }
        if(row0){
            for(int j = 0; j < m; j++)
                matrix[0][j] = 0;
        }
        return;
    }
}

Leetcode–String to Integer (atoi)

The Problem:

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.

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.

Notes:

  1. The key to solve a problem like this is :
    1. clarify the problem, consider how the function would behave for all corner cases. 2. pay attention to details.
  2. One thing to mention for all the conversion to integer: be careful about the range.
    1. Fact: INT_MAX (2147483647) !=  – INT_MIN (-2147483648)

Java Solution

public class Solution {
    public int atoi(String str) {
        int result = 0;
        str =str.trim();
        if(str.length()==0)
            return result;
        boolean neg = false;
        boolean nxtN = false;
        for(int i = 0; i < str.length(); i++){
            if(result==0 && str.charAt(i)=='-'){
                if(nxtN)return 0;
                neg = true;
                nxtN = true;
            }
            else if(result ==0 && str.charAt(i)=='+' ){
                if(nxtN)return 0;
                neg = false;
                nxtN = true;
            }
            //breaks a valid number
            else if(!(str.charAt(i)>='0' && str.charAt(i)<='9')){
                break;
            }
            else if(str.charAt(i)>='0' && str.charAt(i)<='9'){
                nxtN = true;
                int temp = str.charAt(i)-'0';
                // check the integer bound
                // note the condition for temp is > not >=
                // watch out that Integer.MIN_VALUE != -Integer.MAX_VALUE 
                if((result  == (Integer.MAX_VALUE)/10 && temp > (Integer.MAX_VALUE%10))||
                (result > (Integer.MAX_VALUE)/10)){
                        return neg ? Integer.MIN_VALUE: Integer.MAX_VALUE;
                }
                else
                    result = result *10 + temp;
            }
        }
        return neg ? 0-result : result;
    }
}

Leetcode–Valid Parentheses

The Problem:

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.

Notes:

  1. This is a basic problem using stack.

Java Solution

public class Solution {
    public boolean isValid(String s) {
        if(s.length()==0 || s.length()%2==1) return false; 
        Stack<Character> st = new Stack<Character>();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i)=='{' || s.charAt(i)=='[' || s.charAt(i)=='(')
                st.push(s.charAt(i));
            else if(st.empty())
                return false;
            else if(s.charAt(i)=='}'){
                if(st.peek()!= '{')
                    return false;
                else
                    st.pop();
            }
            else if(s.charAt(i)==']'){
                if(st.peek()!='[')
                    return false;
                else 
                    st.pop();
            }
            else if(s.charAt(i)==')'){
                if(st.peek()!='(')
                    return false;
                else 
                    st.pop();
            }
        }
        return st.empty();
    }
}

Leetcode–Distinct Subsequences

The Problem:

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

Notes:

  1. Here when seeing only required to return the number of ways (not the entire list of ways), we could consider DP instead of pure recursion. use match[i][j] to represent number of distinct sub sequence that S[0-i] has for T[0-j] seems a good start.
  2. As for the recurrence formula, if S[i]!=T[j], then simply means S[i] is not used for the match (match[i][j] = match[i-1][j]).  if(S[i]=T[j]), then we can consider the number of ways comes from two paths: use S[i]  (match[i][j] = match[i-1][j-1]); and  not use S[i]  (match[i][j] = match[i-1][j]).
  3. Watch out for the details and edge cases.

Java Solution

public class Solution {
    public int numDistinct(String S, String T) {
        int slen = S.length();
        int tlen = T.length();
        // check length
        if(slen==0 || slen < tlen)
            return 0;
        if(tlen==0)
            return 1;
        // record dist. subseqs of t[0-j] in in s[0-i] in match[i][j]
        int[][] match = new int[slen][tlen];       
        for(int i = 0; i < slen; i++){
            for(int j = 0; j < tlen; j++){
                if(i < j)
                    match[i][j] = 0;
                else if(i==0 && j==0){
                    match[i][j] = S.charAt(0)==T.charAt(0)? 1:0;
                }
                else if(S.charAt(i)==T.charAt(j)){
                    //divide case by either use s[i] or not
                    // only consider j=0 case, i=0 already covered in previous conditions: 
                     //1. i<j  2. i==0&& j==0
                    if(j==0)
                        match[i][j] = match[i-1][j]+1;
                    else
                        match[i][j] = match[i-1][j-1] + match[i-1][j];
                }
                else{
                    match[i][j] = match[i-1][j];
                }
            }
        }
        return match[slen-1][tlen-1];
    }
}