Leetcode–Roman to Integer

The Problem:

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Notes:

  1. First need to know about Roman numbers: I – 1, V – 5, X – 10, L – 50, C – 100, D – 500, M – 1000. For special representation of 4 and 9, it’s simpler to just hard code the rules and insert to the above list. Then only need to check if number > (1000,900,…), if so append a symbol accordingly.
  2. Be careful about checking the range in the match function.

Java Solution

public class Solution {
    public int romanToInt(String s) {
        //I - 1, V - 5, X - 10, L - 50, C - 100, D - 500, M - 1000.
        //only need to check if greater than 10-9-5-4-1
        String[] sym = {"M","CM", "D","CD", "C", "XC", "L", "XL", "X", "IX", "V","IV" ,"I"};
        int[] scale = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        int result = 0;
        int i = 0; 
        int j = 0;
        while( i < s.length()){
            if(match(s, i, sym[j])){
                result += scale[j];
                i+= sym[j].length();
            }
            else{
                j++;
            }
        }
        return result;
    }    
    private boolean match(String a, int id, String b){
        int l = b.length();
        if(a.length()-id < l)return false;
        return b.equals(a.substring(id,id+l));
    }
}
Advertisements

Leetcode–Integer to Roman

The Problem:

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Notes:

  1. First need to know about Roman numbers: I – 1, V – 5, X – 10, L – 50, C – 100, D – 500, M – 1000. For special representation of 4 and 9, it’s simpler to just hard code the rules and insert to the above list. Then only need to check if number > (1000,900,…), if so append a symbol accordingly.

Java Solution

public class Solution {
    public String intToRoman(int num) {
        StringBuffer sb = new StringBuffer();
        //I - 1, V - 5, X - 10, L - 50, C - 100, D - 500, M - 1000.
        //only need to check if greater than 10-9-5-4-1
        String[] sym = {"M","CM", "D","CD", "C", "XC", "L", "XL", "X", "IX", "V","IV" ,"I"};
        int[] scale = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        int i = 0;
        while(i < sym.length){
            if(num >= scale[i]){
                sb.append(sym[i]);
                num -= scale[i];
            }
            else{
                i++;
            }
        }
        return sb.toString();
    }
}

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

Leetcode–Subsets

The Problem:

Given a set of distinct integers, S, return all possible subsets.

Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Notes:

  1. Sort the input list first, and then add each next element to all existing list in result. Remember to add an empty set first.

Java Solution

public class Solution {
    public List<List<Integer>> subsets(int[] S) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        result.add(new ArrayList<Integer>());
        if(S.length==0){
            return result;
        }
        Arrays.sort(S);
        for(int i = 0; i < S.length; i++){
            int len = result.size();
            for(int j = 0; j < len; j++){
                ArrayList<Integer> addlist =  new ArrayList<Integer>(result.get(j));
                addlist.add(S[i]);
                result.add(addlist);
            }
        }
        return result;
    }
}

Leetcode–Anagrams

The Problem:

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Notes:

  1. The key is to sort each string, and use sorted string as the signature to group anagrams.
  2. Use a hashMap to record the list of each group. We can also directly add the anagrams to result list (with some mark to tell if a key in the map has no anagram) since we don’t need to return the result by groups

Java Solution

public class Solution {
    public List<String> anagrams(String[] strs) {
        List<String> result = new ArrayList<String>();
        if(strs.length==0) return result;
        Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        for(int i = 0; i < strs.length; i++){
            char[] arr = strs[i].toCharArray();
            Arrays.sort(arr);
            String newstr = new String(arr);
            if(!map.containsKey(newstr)){
                map.put(newstr, new ArrayList<String>());
            }
            map.get(newstr).add(strs[i]);
        }
        for(ArrayList<String> list : map.values()){
            if(list.size()>=2){
                for(String s : list)
                    result.add(s);
            }
        }
        return result;
    }
}

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