Minimum Window Substring

Problem

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

from https://leetcode.com/problems/minimum-window-substring/

Solution:
There is a very nice post on this problem. Here is the link: http://n00tc0d3r.blogspot.com/2013/04/minimum-window-substring.html

Issue:

One the issue I found when I coded this problem is that I used LinkedList to store the next index of the needed characters. And the system throws an Time Limit Exceeded exception. Then, I start to carefully compare my code with code of the above link. I found the only difference is that that post used ArrayList instead of LinkedList.

Here is the difference between ArrayList and LinkedList
1. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically resizing array
2. LinkedList<E> allows for constant-time insertions or removals using iterators, but only sequential access of elements; ArrayList<E>, on the other hand, allow fast random read access, so you can grab any element in constant time.
3. Also, if you have large lists, keep in mind that memory usage is also different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored. ArrayLists don't have this overhead

Therefore, when you are not sure, start with ArrayList

Edit Distance

Problem:

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Idea:

Think about the sub problems.  for any given length strings, i and j. How to get the min distance.  1) String i, to delete a character,  2) String j, to delete a character, 3) or replace a character.   

So minDistance(i ,j ) = Math.min  0f the following four sub problems

                                  minDistance(i-1,j) +1
                                 minDistance(i,j-1)+1
                                  minDistance(i-1,j-1) +1    if(stringI.charAt(i)!=stringJ.charAt(j)) ,
                                  minDistance(i-1,j-1)          if(stringI.charAt(i)==stringJ.charAt(j))

Then, we can use a two dimensional arrays to solve the problem by filling the array.

Solution:

public class Solution { 

              public int minDistance(String word1, String word2) { 

                      if(word1 == null && word2==null) return 0; if(word1==null) return word2.length();                           if(word2==null) return word1.length(); if(word1.length()==0) return word2.length();                           if(word2.length()==0) return word1.length(); int[][] result=new int[word1.length()][word2.length()]; 

                      result[0][0]=word1.charAt(0)==word2.charAt(0)?0:1; 

                      for(int i =1;i<word2.length();i++){ 

                             if(word2.charAt(i)==word1.charAt(0)){ 

                                     result[0][i]=i; 

                             }else{ result[0][i]=result[0][i-1]+1; } 

                       } 

                       for(int i =1;i<word1.length();i++){ 

                            if(word1.charAt(i)==word2.charAt(0)){ 

                                        result[i][0]=i;

                            }else{ result[i][0]=result[i-1][0]+1; } 

                       } 

                      for(int i=1;i<word1.length();i++){ 

                           for(int j=1;j<word2.length();j++){ 

                                 int localMin1 = Math.min(result[i-1][j]+1,result[i][j-1]+1); 

                                 int tmp=word1.charAt(i)==word2.charAt(j)?result[i-1][j-1]:result[i-1][j-1]+1;                                      result[i][j]=Math.min(localMin1,tmp); } } return result[word1.length()-1][word2.length()-1]; }

                     }

}

Decode Ways

Problem:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

Idea:



Solution: 

public class Solution {
    public int numDecodings(String s) {
        if(s == null || s.length()<1) return 0;
     
        int store[]=new int[s.length()+1];
        store[0]=decodeable(s.substring(0,1))?1:0;
        if(s.length()<2) return store[0];
        store[1]=decodeable(s.substring(1,2))?store[0]:0;
        if(s.length()>1&&decodeable(s.substring(0,2))){
            store[1] +=1;
        }
       
        for(int i =2;i<s.length();i++){
            if(decodeable(s.substring(i,i+1))){
                store[i] = store[i-1];
            }
            if(decodeable(s.substring(i-1,i+1))){
                store[i] +=store[i-2];
            }
        }
       
        return store[s.length()-1];
       
    }
   
    public boolean decodeable(String str){
        int result = 0;
        if(str.charAt(0)=='0') return false;
        for(int i =0;i<str.length();i++){
            result =result *10+str.charAt(i)-'0';
        }
        if(result<=26 && result>0) return true;
        return false;
    }
}

Group Anagrams

The major part is to group strs by the same key. Here I used to a way to sort all the characters, and check whether after sorting, strings have the same key or not. If they have the same key, then they are anagrams. Otherwise, they are not.

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if(strs == null) return null;
        List<List<String>> result =new ArrayList<List<String>>();
        if(strs.length==0) return result;
        HashMap<String, List<String>> map =new HashMap<String, List<String>>();
        for(int i =0;i<strs.length;i++){
            String key = getKey(strs[i]);
            if(map.containsKey(key)){
                List<String> vals = map.get(key);
                vals.add(strs[i]);
            }else{
                List<String> vals = new ArrayList<String>();
                vals.add(strs[i]);
                map.put(key, vals);
            }
        }
        for(Map.Entry<String, List<String>> element:map.entrySet()){
            result.add(element.getValue());
        }
        return result;
    }
 
    String getKey(String str){
        if(str==null || str.length()<=1) return str;
        char[] tmp = str.toCharArray();
        Arrays.sort(tmp);
        return new String(tmp);
    }
}

Generate Parentheses

The basic idea is to use recursive way to generate the parenthesis. When you add one additional parenthesis, check all the potential locations, and check the whether it has appeared before or not.

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        if(n==0) return result;
        if(n==1) {result.add("()");return result;}
        List<String> sub = generateParenthesis(n-1);
        for(String val:sub){
            List<String> tmp = addOneParenthesis(val);
            for(String tmp1:tmp){
                if(!result.contains(tmp1)){
                    result.add(tmp1);
                }
            }
        }
        return result;
    }
   
    private List<String> addOneParenthesis(String val){
        List<String> result =new ArrayList<String>();
        if(val==null || val.isEmpty()){
            return result;
        }
        for(int i =0;i<val.length();i++){
            StringBuffer buf = new StringBuffer();
            buf.append(val.substring(0,i));
            buf.append("()");
            buf.append(val.substring(i,val.length()));
            result.add(buf.toString());
        }
        return result;
    }
}

Letter Combinations of a Phone Number

My java solution.

The basic idea is to have a helper function to get the corresponding characters for each digit; then use for-loops to get the combinations

public class Solution {
    // have a helper function to get all the corresponding letters, and then combine the result togeter by StringBuffer.
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<String>();
        if(digits ==null ||digits.length()==0) return res;
        for(int i=0;i<digits.length();i++){
            List<Character> resChars=getChars(digits.charAt(i));
            if(res.size()==0){
                for(int j =0;j<resChars.size();j++){
                    res.add(resChars.get(j)+"");
                }
            }else{
                List<String> restmp = new ArrayList<String>();
                for(int p =0;p<res.size();p++){
                    for(int q =0;q<resChars.size();q++){
                        restmp.add(res.get(p)+resChars.get(q));
                    }
                }
                res=restmp;
            }
        }
        return res;
    }
   
    List<Character> getChars(char digit){
        List<Character> res = new ArrayList<Character>();
       
        switch(digit){
            case '2': res.add('a');res.add('b');res.add('c');break;
            case '3': res.add('d');res.add('e');res.add('f');break;
            case '4': res.add('g');res.add('h');res.add('i');break;
            case '5': res.add('j');res.add('k');res.add('l');break;
            case '6': res.add('m');res.add('n');res.add('o');break;
            case '7': res.add('p');res.add('q');res.add('r');res.add('s');break;
            case '8': res.add('t');res.add('u');res.add('v');break;
            case '9': res.add('w');res.add('x');res.add('y');res.add('z');break;
            default:break;
        }
       
        return res;
    }
}