LeetCode Max Rectangle Area

Same idea of Max area in a histgram.

But we need a array to store the height of each row. We dont need calculate the height every time.
Just check the current character and the previous height. we can get the height array.

Here is the code.
public int maximalRectangle(char[][] matrix) {
        if (matrix==null || matrix.length==0 || matrix[0].length==0) return 0;
        int maxArea = 0;
        int[] height = new int[matrix[0].length];
        for (int i=0; i<matrix.length; i++) {
            for (int j=0; j<matrix[0].length; j++) {
                height[j] = matrix[i][j] == '0' ? 0 : height[j]+1;
            }
            maxArea = Math.max(maxArea, calMaxArea(height));
        }
        return maxArea;
    }
   
    private int calMaxArea(int[] height) {
        Stack<Integer> stack = new Stack<Integer>();
        int maxArea = 0;
        int i=0;
        int[] h = new int[height.length+1];
        h = Arrays.copyOf(height, height.length+1);
        while (i<h.length) {
            if (stack.isEmpty() || h[stack.peek()]<=h[i]) {
                stack.push(i++);
            } else {
                int t = stack.pop();
                maxArea = Math.max(maxArea, h[t] * (stack.isEmpty() ? i : i-stack.peek()-1));
            }
        }
       
        return maxArea;
    }

LeetCode Largest Rectangle in Histogram

Here is the link for the explanation.

http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html


public int largestRectangleArea(int[] height) {
     Stack<Integer> stack = new Stack<Integer>();
     int i = 0;
     int maxArea = 0;
     int[] h = new int[height.length+1];
     h = Arrays.copyOf(height, height.length+1);
   
     while (i<h.length) {
         if (stack.isEmpty() || h[stack.peek()] <= h[i]) {
             stack.push(i++);
         } else {
             int t = stack.pop();
             maxArea = Math.max(maxArea, h[t]* (stack.isEmpty()? i : i-stack.peek()-1));
         }
     }
     return maxArea;
    }

Remove Duplicates from Sorted List II

skip all the duplicate and use prev and curr and update these two.


public ListNode deleteDuplicates(ListNode head) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if (head == null || head.next == null) return head;
       
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
       
        while (curr!=null) {
            while (curr.next!=null && prev.next.val == curr.next.val) {
                curr = curr.next;
            }
           
            if (prev.next == curr) {
                prev = curr;
            } else {
                prev.next = curr.next;
            }
            curr = curr.next;
        }
        return dummy.next;

    }

Minimum Window Substring LeetCode

Idea is simple. Using a hashmap to store the number of elements in T.
Scan S by using two pointers.

public String minWindow(String S, String T) {
        if (S==null || S.length()==0) return "";
        //Put all the elements in the hashmap
        Map<Character, Integer> map = new HashMap<>();
        for (int i=0; i<T.length(); i++) {
            if (map.containsKey(T.charAt(i))) {
                map.put(T.charAt(i), map.get(T.charAt(i))+1);
            } else {
                map.put(T.charAt(i), 1);
            }
        }
       
        //Scan the String S
        int left = 0, right = 0, count = 0, minStart = 0, minLen = S.length()+1; //Initial value is larger than S
        for (; right<S.length(); right++) {
            if (map.containsKey(S.charAt(right))) {
                map.put(S.charAt(right), map.get(S.charAt(right))-1);
                if (map.get(S.charAt(right))>= 0) {
                    count++;
                }
                while (count == T.length()) {
                    if (right - left + 1 < minLen) {
                        minLen = right - left + 1;
                        minStart = left;
                    }
               
                if (map.containsKey(S.charAt(left))) {
                    map.put(S.charAt(left), map.get(S.charAt(left))+1);
                    if (map.get(S.charAt(left))>0) {
                        count--;
                    }
                }
                    left++;
                }
            }
        }
       
        //Special case: could not find the T
        if (minLen > S.length()) {
            return "";
        }
        return S.substring(minStart, minStart+minLen);
    }

Edit distance LeetCode

1. word1.charAt(i) == word2.charAt(j) dp[i][j] = dp[i-1][j-1];
2. word1.charAt(i) != word2.charAt(j) dp[i][j]  = 1+ min {dp[i][j-1], dp[i-1][j], dp[i-1][j-1]}

public int minDistance(String word1, String word2) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int len1 = word1.length();
        int len2 = word2.length();
int[][] dp = new int[len1 + 1][len2 + 1];

   for (int i=0; i<=len1; i++) {
       dp[i][0] = i;
   }
   for (int j=0; j<=len2; j++) {
       dp[0][j] = j;
   }
   
   for (int i=1; i<=len1; i++) {
       for (int j=1; j<=len2; j++) {
           if (word1.charAt(i-1) == word2.charAt(j-1)) {
               dp[i][j] = dp[i-1][j-1];
           } else {
               int temp = Math.min(dp[i-1][j], dp[i][j-1]);
               dp[i][j] = 1 + Math.min(dp[i-1][j-1], temp);
           }
       }
   }
   return dp[len1][len2];
    }

Here is the solution from the Wiki.
http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance

 private static int minimum(int a, int b, int c) {                            
        return Math.min(Math.min(a, b), c);                                      
    }                                                                            
 
    public static int computeLevenshteinDistance(String str1,String str2) {      
        int[][] distance = new int[str1.length() + 1][str2.length() + 1];        
 
        for (int i = 0; i <= str1.length(); i++)                                 
            distance[i][0] = i;                                                  
        for (int j = 1; j <= str2.length(); j++)                                 
            distance[0][j] = j;                                                  
 
        for (int i = 1; i <= str1.length(); i++)                                 
            for (int j = 1; j <= str2.length(); j++)                             
                distance[i][j] = minimum(                                        
                        distance[i - 1][j] + 1,                                  
                        distance[i][j - 1] + 1,                                  
                        distance[i - 1][j - 1] + ((str1.charAt(i - 1) == str2.charAt(j - 1)) ? 0 : 1));
 
        return distance[str1.length()][str2.length()];                           
    }                                                                            

Given a better solution with Space Complexity O(n) and Time Complexity O(m);

public int LevenshteinDistance (String s0, String s1) {                          
    int len0 = s0.length() + 1;                                                     
    int len1 = s1.length() + 1;                                                     
 
    // the array of distances                                                       
    int[] cost = new int[len0];                                                     
    int[] newcost = new int[len0];                                                  
 
    // initial cost of skipping prefix in String s0                                 
    for (int i = 0; i < len0; i++) cost[i] = i;                                     
 
    // dynamically computing the array of distances                                  
 
    // transformation cost for each letter in s1                                    
    for (int j = 1; j < len1; j++) {                                                
        // initial cost of skipping prefix in String s1                             
        newcost[0] = j;                                                             
 
        // transformation cost for each letter in s0                                
        for(int i = 1; i < len0; i++) {                                             
            // matching current letters in both strings                             
            int match = (s0.charAt(i - 1) == s1.charAt(j - 1)) ? 0 : 1;             
 
            // computing cost for each transformation                               
            int cost_replace = cost[i - 1] + match;                                 
            int cost_insert  = cost[i] + 1;                                         
            int cost_delete  = newcost[i - 1] + 1;                                  
 
            // keep minimum cost                                                    
            newcost[i] = Math.min(Math.min(cost_insert, cost_delete), cost_replace);
        }                                                                           
 
        // swap cost/newcost arrays                                                 
        int[] swap = cost; cost = newcost; newcost = swap;                          
    }                                                                               
 
    // the distance is the cost for transforming all letters in both strings        
    return cost[len0 - 1];                                                          
}

Simplify Path LeetCode

Use stack to store the string between "/".
Similiar idea with Valid parentheses, reverse polish notation.
public String simplifyPath(String path) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
      if (path==null || path.length()==0) return "/";
     
      Stack<String> stack = new Stack<String>();
      String[] splits = path.trim().split("/");
     
      for (String str : splits) {
          if (str==null || str.length()==0 || str.equals(".")) {
             
          } else if (str.equals("..")) {
              if (stack.size() > 0) stack.pop();
          } else {
              stack.push(str);
          }
      }
     
      if (stack.isEmpty()) return "/";
      StringBuilder sb = new StringBuilder();
      while (!stack.isEmpty()) {
          sb.insert(0, stack.pop());
          sb.insert(0, "/");
      }
      return sb.toString();
    }

Text Justification LeetCode

X stands for the space.
ThisXXisXanXexample.

currList only contains the non-first words.
So in the currList it will be "Xis" "Xan" "Xexample".

The example showing in the leetcode is not accurate. We should put spaces in front of the first word.


public List<String> fullJustify(String[] words, int L) {
        List<String> currList = new ArrayList<String>();
        List<String> res = new ArrayList<String>();
        int counts=0, len=0;
        StringBuilder sb = new StringBuilder();
     
        while (counts < words.length) {
            //1 put the first word into the line
            sb.setLength(0);
            sb.append(words[counts]);
            currList.clear();
            len = words[counts].length();
            counts++;
         
            //2. Handle the rest of the words for each line
            while (counts<words.length && len+1+words[counts].length()<=L) {
                currList.add(" " + words[counts]);
                len += words[counts].length()+1;
                counts++;
            }
         
            //3. Calculate the number of spaces we need and insert into the currList
            if (counts<words.length && currList.size()>0) {
                int numSpaces = L-len;
                int avg = numSpaces/currList.size();
                int rem = numSpaces%currList.size();
                for (int i=0; i<currList.size(); i++) {
                    appendSpace(sb, i<rem ? avg+1 : avg);
                    sb.append(currList.get(i));
                }
            } else {
                //4. Special case for the last line
                for (int j=0; j<currList.size(); j++) {
                    sb.append(currList.get(j));
                }
                    appendSpace(sb, L-len);
            }
                res.add(sb.toString());
        }
        return res;
    }
 
    private void appendSpace(StringBuilder sb, int n) {
        for (int i=0; i<n; i++) {
            sb.append(" ");
        }
    }

Minimum Path Sum LeetCode

First, I try to use the m by n matrix to store the minimum distance to the top-left corner.
Second, we optimize the space from m*n to n. We only store the minimum distance for the current row.


public int minPathSum(int[][] grid) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       int m = grid.length;
       int n= grid[0].length;
     
       int[] G = new int[n];
     
       for (int i=0; i<m; i++) {
           for (int j=0; j<n; j++) {
               if (j==0) {
                   G[j] += grid[i][j];
               } else if (i==0) {
                   G[j] = G[j-1] + grid[i][j];
               } else {
                   G[j] = Math.min(G[j-1], G[j]) + grid[i][j];
               }
           }
       }
       return G[n-1];
    }