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

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