Leetcode–Sum Root to Leaf Numbers

The Problem:

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Notes:

  1. This is a basic tree traversal problem. The key is to only add to final output at leaf nodes.

Java Solution

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int sum = 0;
    public int sumNumbers(TreeNode root) {
        if(root==null)
            return 0;
        sumPath(root, 0);
        return sum;
    }
    
    public void sumPath(TreeNode root, int pass){
        if(root.left==null && root.right==null){
            // leaf node, add to final result
            sum+= 10 * pass + root.val;
        }
        else {
            if(root.left!= null){
                 sumPath(root.left, 10 * pass + root.val);
            }
             if(root.right!= null){
                 sumPath(root.right, 10 * pass + root.val);
            }
        }
    }
}
Advertisements

Leetcode–Generate Parentheses

The Problem:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

 

Notes:

  1. I tried to derived the list of n from list of n-1, then found it’s not that easy! Try a different approach which is much simpler: Add a ‘(‘ if number of left not reach n, and add a ‘)’ if left more than right.

Java Solution

public class Solution {
    List<String> result;
    public List<String> generateParenthesis(int n) {
        result = new ArrayList<String>();
        if(n==0)
            return result;
        gp(1, 1, n, "(");
        return result;
    }
    public void gp(int left, int lSubR, int n, String str){
        if(left==n && lSubR==0){// a valid string
            result.add(str);
        }
        else if(left==n){
            gp(left, lSubR-1, n, str+")");
        }
        else if(left < n){
            gp(left+1, lSubR+1, n, str+"(");
            if(lSubR > 0){
                gp(left, lSubR-1, n, str+")");
            }
        }    
    }
    
}

Leetcode–Word Ladder

The Problem:

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Notes:

  1. At first I was considering using recursion, which results in a “DFS” structure, and need to keep track of min steps, because it may already traverse down too far in one recursion then reach the end, yet in other branches may only need much fewer steps. This is an indication that we should use “BFS” instead.
  2. When using BFS, we need 3 things:
    1. a queue to hold “next start”
    2. a set to record the strings already visited, to avoid trapped in a loop
    3. since we need to return the steps, it needs to pair with the string in queue. So I used a wrapper class.

Java Solution I-DFS

public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
        if(start.equals(end)) return 1;
        char[] arr = start.toCharArray();
        int min = Integer.MAX_VALUE;
        for(int i = 0; i <start.length(); i++){
            char temp = arr[i];
            for(char ch = 'a'; ch <='z'; ch++){
                if(ch != temp){
                    arr[i] = ch;
                    String nxt = new String(arr);
                    if(end.equals(nxt))
                        return 2;
                    else if(dict.contains(nxt)){
                        dict.remove(nxt);
                        min = Math.min(min, 1+ ladderLength(nxt, end, dict));
                        dict.add(nxt);
                    }
                }
            }
            arr[i] = temp;
        }
        return min==Integer.MAX_VALUE ? 0:min;
    }
}

Java Solution II-BFS

public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
        if(start.equals(end)) return 1;
        Queue<WrapStr> q = new LinkedList<WrapStr>();
        Set<String> visited = new HashSet<String>();
        q.add(new WrapStr(start, 1));
        visited.add(start);
        while(!q.isEmpty()){
            WrapStr wp = q.poll();
            char[] arr = wp.str.toCharArray();
            for(int i = 0; i <arr.length; i++){
                char temp = arr[i];
                for(char ch = 'a'; ch <='z'; ch++){
                    if(ch != temp){
                        arr[i] = ch;
                        String nxt = new String(arr);
                        if(end.equals(nxt))
                            return wp.steps+1;
                        else if(!visited.contains(nxt) && dict.contains(nxt)){
                            q.add(new WrapStr(nxt, wp.steps+1));
                            visited.add(nxt);
                        }
                    }
                }
                arr[i] = temp;
            }
        }
        return 0;        
    }
}
class WrapStr{
    public String str;
    public int steps;
    public WrapStr(String s, int l){
        str = s;
        steps = l;
    }
}

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

Leetcode–Scramble String

The Problem:

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Notes:

  1. A recursion problem, try each substring  see if a) s1.sub1 match s2.sub1, and s1.sub2 match s2.sub2; OR b) s1.sub1 match s2.sub2 and s1.sub2 match s2.sub1
  2. Add conditions pre-check length and characters before going to recursion.

Java Solution

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if((s1.length()==0 && s2.length()==0)|| s1.equals(s2))
            return true;
        if(s1.length()!=s2.length())
            return false;
        if(!sameChar(s1,s2))
            return false;
            
        for(int i = 1; i < s1.length(); i++){
            if((isScramble(s1.substring(0,i),s2.substring(0,i)) && isScramble(s1.substring(i), s2.substring(i)))||
            (isScramble(s1.substring(0, i),s2.substring(s2.length()-i)) && isScramble(s1.substring(i), s2.substring(0,s2.length()-i))))
                return true;
        }
        return false;
        
    }
    
    private boolean sameChar(String s1, String s2){
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();
        Arrays.sort(ch1);
        Arrays.sort(ch2);
        return new String(ch1).equals(new String(ch2));
    }
}

Leetcode–Wildcard Matching

The Problem:

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

Notes:

  1. I used a pretty straightforward recursive solution but exceeds time limit. Here is a iterative solution, it records the index of both p and s whenever a * occurs in p, and if this round goes to a dead end, start from the recorded indices.

Java Solution

public class Solution {
    public boolean isMatch(String s, String p) {
        int slen = s.length();
        int plen = p.length();
 
        if(plen==0){
            if(slen==0)return true;
            else return false;
        }
        
        int i = 0;
        int j = 0;
        int nxts = -1;
        int nxtp = -1;
//here only use i as ending condition, for the case j reach the end with no match, 
//it can go back to recorded index and match again
while(i < slen){
            if  (j < plen && (p.charAt(j)=='?' || p.charAt(j)==s.charAt(i)))
            {
                i++;
                j++;
            } 
            else if(j < plen && p.charAt(j)=='*'){
                nxtp = j;
                nxts = i;
//only increase j
                j++;
            }
            else {
                if(nxtp==-1){
                    return false;
                }
                else{
                    nxts++;
                    i = nxts;
// only increase i by 1 from previous recorded index, 
//which means include s[i] to the match of *
//(not set i up to the failure point)
                    j = nxtp+1;
                }
            }
        }
//if p has character left, only can be true if all the left are *
        while(j < plen && p.charAt(j)=='*'){
            j++;
        }
        
        return (j==plen);
   }
}
      

Leetcode–Regular Expression Matching

The Problem:

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Notes:

  1. Note that for each pair of “?*” in p, there is a possible match of skipping this pair in p.
  2. Design the branch condition as:
    1. p[1] !=’*’, which means if p[0] not match then can directly return false;
    2. otherwise, need to consider the ‘?*’ skipping cases:
      1. directly skip by going to p[2]
      2. traversing s while s[id] match p[0], and for each match also consider a skip to p[2]

Java Solution

public class Solution {
    public boolean isMatch(String s, String p) {
        if(s.length()==0 &&  p.length()==0)
            return true;
        if( p.length()==0) 
            return false;
        // check if not have a P:"x*" condition, then the first char must match      
        if(p.length()==1 ||  p.charAt(1)!='*'){
            if(s.length() >0 && (p.charAt(0)=='.' || s.charAt(0) == p.charAt(0))){
               return isMatch(s.substring(1),p.substring(1));
            }
            else
                return false;
        }
        else{
        // for condition: P:"x*", need to consider skipping each pair of "x*"
            //directly skip
            if(isMatch(s, p.substring(2)))
                return true;
            //for each match of s[id] and p:x, try a skip 
            int id = 0;
            while(id < s.length()){
                if(s.charAt(id)==p.charAt(0) || p.charAt(0)=='.'){
                    if(isMatch(s.substring(id+1), p.substring(2)))
                        return true;
                }
                else{
                    break;
                }
                id++;       
            }
            return false;
        }
    }
}