[LeetCode java solution] – String/Hashtable – Anagrams

Problem:

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

Note: All inputs will be in lower-case.

Method:

Create a HashMap:

key: String (after chars are sorted);

value: The specific corresponding string.

Then, iterate through the HashMap. If there is a key with more than two values, we add them into the result container.

Code:

public class Solution {
    public ArrayList<String> anagrams(String[] strs) {
        if (strs == null || strs.length == 0) return null;
        ArrayList<String> res = new ArrayList<String>();
        
        HashMap<String, ArrayList<String>> dict = new HashMap<String, ArrayList<String>>();
        
        for (int i = 0; i < strs.length; i++){
            char[] c = strs[i].toCharArray();
            Arrays.sort(c);
            String s = new String(c);
            if (dict.containsKey(s)){
                dict.get(s).add(strs[i]);
            }else{
                ArrayList<String> l = new ArrayList<String>();
                l.add(strs[i]);
                dict.put(s,l);
            }
        }
        Iterator iter = dict.values().iterator();
        while(iter.hasNext()){
            ArrayList<String> temp = (ArrayList<String>)iter.next();  //cast type!!
            if(temp.size() > 1){
              res.addAll(temp);
            }
        }
        return res;
    }
}

[LeetCode Java Solution] – String/DFS – Generate Parentheses

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:

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

Method:

How to understand DFS? Determine how many branches we have? For each branch, we call recursive helper method. So overall, we will find out all the solutions for one branch and then go to another branch and do the same thing.

Remember: in each level, we have to make sure the variables are not changed, since we still need to go to the next branch.

Code:

public class Solution {
    ArrayList<String> res = new ArrayList<String>();
    
    public ArrayList<String> generateParenthesis(int n) {
        if (n == 0) return res;
        helper(n, n, "");
        return res;
    }
    
    public void helper(int left, int right, String item){
        if (left > right) return;
        if (left == 0 && right == 0){
            res.add(item);
        }
        if (left > 0){
            helper(left-1, right, item + "(");
            // remember that one each level, you can't change the variables.
        }
        if (right > 0){
            helper(left, right-1, item + ")");
        }
    }
}

[LeetCode Java Solution] – Math/String – Roman to Integer

Problem:

Given a roman numeral, convert it to an integer.

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

Method:

1. This problem has to use HashMap, since we need to quickly look up what does each character mean.

2. Thoughts: if the current char has greater or equal value than the next char, add it; else, minus it.

Code:

public class Solution {
    public int romanToInt(String s) {
        HashMap<Character, Integer> dict = new HashMap<Character, Integer>();
        dict.put('I',1);
        dict.put('V',5);
        dict.put('X',10);
        dict.put('L',50);
        dict.put('C',100);
        dict.put('D',500);
        dict.put('M',1000);
        
        int res = 0;
        
        int i = 0;
        
        for (i = 0; i < s.length()-1; i++){
            if (dict.get(s.charAt(i)) >= dict.get(s.charAt(i+1))){
                res += dict.get(s.charAt(i));
            }else{
                res -= dict.get(s.charAt(i));
            }
        }
        
       res += dict.get(s.charAt(i));
       return res;
        
    }
}

[LeetCode] – Math/String – Integer to Roman

Problem:

Given an integer, convert it to a roman numeral.

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

Related Knowledge:

Roman Numbers:

I (1)

V (5)

X (10)

L (50)

C (100)

D (500)

M (1000)

Method:

The tricky is how to prepare the array. Consider there are totally 13 characters in roman number.

String[] str = {“M”,”CM”,”D”,”CD”,”C”,”XC”,”L”,”XL”,”X”,”IX”,”V”,”IV”,”I”};
int[] digit = {1000,900,500,400,100,90,50,40,10,9,5,4,1};

Code:

public class Solution {
    public String intToRoman(int num) {
        String[] str = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        int[] n = {1000,900,500,400,100,90,50,40,10,9,5,4,1 };
        StringBuilder s = new StringBuilder();
        
        for (int i = 0; i < str.length; i++){
            int repeat = num/n[i];
            
            for (; repeat >0; repeat--){
                s.append(str[i]);
            }
            num = num % n[i];
        }
        
        return new String(s);
    }
}

Method 2:

Get all digits into an ArrayList (Only 4 digits, since all < 3999). And then get one digit, append several strings.

1-3: use ‘one’

4: one + five

5: five

6-8: five +one

9: one + ten

The above rules apply for all 4 digits.

Code for method 2:

public class Solution {
    public String intToRoman(int num) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        int digit = 1000;
        while (digit > 0){
            res.add(num/digit);
            num = num % digit;
            digit = digit / 10;
        }
        StringBuilder s = new StringBuilder();
        
        s.append(convert(res.get(0),"M","",""));
        s.append(convert(res.get(1),"C","D","M"));
        s.append(convert(res.get(2),"X","L","C"));
        s.append(convert(res.get(3),"I","V","X"));
        
        return s.toString();
    }
    
    public String convert(int digit, String one, String five, String ten){
        switch (digit){
            case 0: break;
            case 1: return one;
            case 2: return one.concat(one);
            case 3: return one.concat(one).concat(one);
            case 4: return one.concat(five);
            case 5: return five;
            case 6: return five.concat(one);
            case 7: return five.concat(one).concat(one);
            case 8: return five.concat(one).concat(one).concat(one);
            case 9: return one.concat(ten);
        }
        return "";
    }
}