27. Remove Element Leetcode Java

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Solution:

This problem is very similar to 26. Remove Duplicates from Sorted Array Leetcode  Instead of maintaining an non-duplicates index, we maintain the index for the elements which are not equal to the target value. The code is also very similar.

 if(A==null || A.length==0) return 0;  
    int ind=0;  
    for(int i=0;i<A.length;i++){  
      if(A[i]!=elem){  
        A[ind]=A[i];  
        ind++;  
      }  
    }  
    return ind;  
   }  

26. Remove Duplicates from Sorted Array Leetcode Java

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

Solution:

The algorithm is to maintain a non duplicates elements index, move non-duplicate elements to the index position. After one time iteration all elements from 0 to our index will be non-duplicates.

 public int removeDuplicates(int[] A) {  
    if(A==null || A.length==0) return 0;  
    int index=1;  
    for(int i=1;i<A.length;i++){  
      if(A[i]!=A[i-1]){  
        A[index]=A[i];  
        index++;  
      }  
    }  
    return index;  
   }  

25. Reverse Nodes in k-Group Leetcode Java

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Solution:

This problem is a general problem of 24. Swap Nodes in Pairs Leetcode . Instead of swapping two nodes a time, now we need to swap k nodes each time. The idea is find the pre and end node of the k-group nodes, and do the reverse for those nodes. The reverse is simple, insert each processing node in between the pre node and the pre.next node. Here I use a runner node to find the kth node from the pre. 

 public ListNode reverseKGroup(ListNode head, int k) {  
    if(head==null || k<=1) return head;  
    ListNode predummy=new ListNode(0);  
    predummy.next=head;  
    ListNode pre=predummy;  
    ListNode cur=head;  
    while(pre!=null && pre.next!=null){  
      ListNode runner=pre;  
      for(int i=0;i<k && runner!=null;i++) runner=runner.next;  
      if(runner==null) return predummy.next;  
      ListNode newPre=cur;  
      ListNode end=runner.next;  
      while(cur!=end){  
        ListNode temp=cur.next;  
        cur.next=pre.next;  
        pre.next=cur;  
        cur=temp;  
      }  
      newPre.next=cur;  
      pre=newPre;  
    }  
    return predummy.next;  
   }  

Another simple solution is to maintain a stack with size k. Push the node to the stack till its size reaches k, then pop all the elements out from the stack, which is also the process of reversing the k-group nodes. 

 public ListNode reverseKGroup(ListNode head, int k) {  
     if (k<2) return head;  
     ListNode preDummy=new ListNode(0);  
     preDummy.next=head;  
     ListNode pre=preDummy;  
     Stack<ListNode> sl=new Stack<ListNode>();  
     int i=1;  
     while (head!=null){  
       if(i%k!=0){  
         sl.push(head);  
         head=head.next;  
         i++;  
       }  
       else {  
         pre.next=head;  
         pre=pre.next;  
         head=head.next;  
         while (!sl.isEmpty()){  
           ListNode temp=sl.pop();  
           pre.next=temp;  
           pre=pre.next;  
         }  
         pre.next=head;  
         i++;  
       }  
     }  
     return preDummy.next;  
   }  

24. Swap Nodes in Pairs Leetcode Java

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Solution:

Transverse two nodes each time, maintain a pre pointer, do the swap each time when there is still two or more nodes after pre node. The swap is straightforward, for example to swap 1->2,->3 and assume there is a pre node before the node 1. cur=1, pre.next=1.next(:2), 1.next=1.next.next(:3), pre.next.next(:2.next)=cur(:1), pre=cur(:1) after doing this: oldpre->2->1->3, and the current pre node is becoming 1 node.

A little trick here is to build a dummypre node and put its next as the original head, by doing this, we can avoid a lot of trouble for taking care of the head corner case. And also it is very helpful for final result return.

 public ListNode swapPairs(ListNode head) {  
    if(head==null || head.next==null) return head;  
    ListNode predummy=new ListNode(0);  
    predummy.next=head;  
    ListNode pre=predummy;  
    while(pre.next!=null && pre.next.next!=null){  
      ListNode cur=pre.next;  
      pre.next=cur.next;  
      cur.next=cur.next.next;  
      pre.next.next=cur;  
      pre=cur;  
    }  
    return predummy.next;  
   }  

23. Merge k Sorted Lists Leetcode Java

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Solution:
1.Divide and Conquer
This solution is very similar to the merge sort. Basically it divided the list to two halfs and then merge the first half list to a linked list and merge the second half list to another linked list, then merge the two linked list together. So we have a merge two linked list sub-method called merge(),and we have a recursively divide and merge sub-method called helper(). 
Set the maximum length among all the K linked lists is n. So the merge() will take O(n*K).
The recursion equation is T(K)= 2T(K/2)+O(n*K), so the time complexity is O(nK*logK) according to the master theorem. The space complexity is O(logK) which is the size of the recursion stack.

 public ListNode mergeKLists(List<ListNode> lists) {  
     if(lists==null || lists.size()==0) return null;  
     return helper(lists,0,lists.size()-1);  
   }  
   public ListNode helper(List<ListNode> lists, int l, int r){  
     if(l==r) return lists.get(l);  
     int m=(r-l)/2+l;  
     return merge(helper(lists,l,m),helper(lists,m+1,r));  
   }  
   public ListNode merge(ListNode headA, ListNode headB){  
     ListNode predummy=new ListNode(0);  
     predummy.next=headA;  
     ListNode pre=predummy;  
     while(headA!=null && headB!=null){  
       if(headB.val<headA.val){  
         ListNode temp=headB.next;  
         pre.next=headB;  
         headB.next=headA;  
         headB=temp;  
       }  
       else headA=headA.next;  
      pre=pre.next;  
     }  
     if(headB!=null) pre.next=headB;  
     return predummy.next;      
   }  

2. PriorityQueue Heap
We maintain a priorityqueue to store the listNode based on the value. The head of this queue is always the smallest one in this queue. Because the link lists are sorted, so we only need to add the subsequent node to the heap when its preceding node is retrieved. The size of the priorityqueue is K. To heapify up: insert/offer a new element will take O(logK) while to heapify down: remove/poll the minimum element will also take O(logK). 
So the total time complexity is (nK*O(logK)) for total O(n*K) listNodes. The space is the the size of the priorityqueue: O(K).

 public ListNode mergeKLists(List<ListNode> lists) {  
     if(lists==null || lists.size()==0) return null;  
     PriorityQueue<ListNode> pq=new PriorityQueue<ListNode>(10,new Comparator<ListNode>(){  
       @Override  
       public int compare(ListNode l1, ListNode l2){  
         return l1.val-l2.val;  
       }   
     });  
     for(ListNode ls : lists){  
       if(ls!=null) pq.offer(ls);  
     }  
     ListNode predummy=new ListNode(0);  
     ListNode pre=predummy;  
     while(!pq.isEmpty()){  
       ListNode temp=pq.poll();  
       pre.next=temp;  
       pre=pre.next;  
       if(temp.next!=null) pq.offer(temp.next);   
     }  
     pre.next=null;  
     return predummy.next;  
   }  

17. Letter Combinations of a Phone Number Leetcode Java

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution:

1. Recursion and backtrack solution

Read the number digit one by one recursively and put the corresponding letter one by one to result string and process the next number digit until the end of the string. Add the result string to the result list.  Then backtrack to last digit and add next letter to result string until all the result strings are captured.

  public List<String> letterCombinations(String digits) {  
     List<String> res=new ArrayList<String>();  
     if(digits==null) return res;  
     String[] pad={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};  
     StringBuilder item=new StringBuilder();  
     helper(0,digits,pad,res,item);  
     return res;  
   }  
   public void helper(int ind,String digits,String[] pad, List<String> res,StringBuilder item){  
     if(ind==digits.length()){  
       res.add(item.toString());  
       return;  
     }  
     String letters=pad[digits.charAt(ind)-'2'];  
     for(int i=0;i<letters.length();i++){  
       item.append(letters.charAt(i));  
       helper(ind+1,digits,pad,res,item);  
       item.deleteCharAt(item.length()-1);  
     }  
   }  

1. Iteration solution
Sometime the interviewer may want you give the both iteration solution and the recursion solution. The iteration solution is to add each letter of the number digit to result list each time processing the new number digit. For example, "23", after the first iteration, the result list would be like{"a","b","c"}, the second iteration for processing "3", will add the corresponding letters to the existing result string in the result list {"ad","bd","cd", "ae","be",...."cf"}

 public List<String> letterCombinations(String digits) {  
    if(digits==null) return null;  
    List<String> res= new ArrayList<String>();  
    res.add("");  
    String[] letters={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};  
    for(int i=0;i<digits.length();i++){  
      String letter=letters[digits.charAt(i)-'2'];  
      List<String> newRes=new ArrayList<String>();  
      for(int j=0; j<letter.length();j++){  
        for(String s: res){  
          s+=letter.charAt(j);  
          newRes.add(s);  
        }  
      }  
      res=newRes;  
    }  
    return res;  
   }  

22. Generate Parentheses Leetcode Java

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:

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

Solution:
Recursion and backtracking.
Use two variables l and r to track the remaining amount of left and right parentheses. During the recursion, either left or right can be put into the string depends on the current situation. Several rules must be followed. First, if now l==r, we can't put right one, so r must >= l. Second, l and r must both >=0, so if l==0, only right one can be append to the string. Third: the base case: when l==r==0, add the string to the result set.
Time complexity: Result-Oriented.

 public List<String> generateParenthesis(int n) {  
     List<String> res=new ArrayList<String>();  
     if(n==0) return res;  
     StringBuilder sb=new StringBuilder();  
     helper(n,n,sb,res);  
     return res;  
   }  
   public void helper(int l,int r, StringBuilder sb, List<String> res){  
     if(l==0 && r==0){  
       res.add(sb.toString());  
       return;  
     }  
     if(r<l) return;  
     if(l>0){  
       sb.append('(');  
       helper(l-1,r,sb,res);  
       sb.deleteCharAt(sb.length()-1);  
     }  
     if (r>0){  
       sb.append(')');  
       helper(l,r-1,sb,res);  
       sb.deleteCharAt(sb.length()-1);  
     }  
   }  

20. Valid Parentheses Leetcode Java

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Solution:

A stack is used to track all the left parentheses that has not been paired. Any current right parentheses has to be paired with the top left parentheses of the stack. If not,then the string is not a valid one.
Because the difference of ASCII code between paired parentheses is either 1 or 2, I use this to check if they are paired or not. I assume all chars of this string are parentheses symbols. 

Time complexity: O(n), Space complexity: O(n)

 public boolean isValid(String s) {  
    if(s==null || s.length()==0) return true;  
    Stack<Character> st=new Stack<Character>();  
    for(int i=0;i<s.length();i++){  
      char temp=s.charAt(i);  
      if(temp=='(' ||temp =='{'|| temp=='[') st.push(temp);  
      else {  
        if(st.isEmpty()) return false;  
        int diff=temp-st.pop();  
        if(diff!=1&&diff!=2) return false;  
      }  
    }  
    return st.isEmpty();  
   }  

19. Remove Nth Node From End of List Leetcode Java

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.

Solution:

walker-runner trick.

This is commonly used in linked list problems. Runner is a pointer transverse the list faster or earlier. In this problem, runner is n positions earlier than walker, so when runner hits the end of the list, while walker is (n+1)th node from the end of the list, the previous node of nth node that we try to delete. In order to delete a specific node,we have to find the previous one in singly linked list. By this technique, we can delete the unwanted node only in one pass.

Time complexity: O(n)

 public ListNode removeNthFromEnd(ListNode head, int n) {  
     if(n<=0) return head;  
    ListNode predummy=new ListNode(0);  
    predummy.next=head;  
    ListNode walker=predummy;  
    ListNode runner=predummy;  
    for(int i=0;i<n&& runner!=null;i++) runner=runner.next;  
    if(runner==null) return head;  
    while(runner.next!=null){  
      walker=walker.next;  
      runner=runner.next;  
    }  
    ListNode temp=walker.next;  
    walker.next=temp.next;  
    temp.next=null;  
    return predummy.next;  
   }  

18. 4Sum Leetcode Java

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

Solution:
Two pointer:
Very similar to 3Sum, just add another pointer to track the 4th number.
Time complexity: O(n^3)

  public List<List<Integer>> fourSum(int[] num, int target) {  
    List<List<Integer>> res=new ArrayList<List<Integer>>();  
    if(num==null || num.length<4) return res;  
    Arrays.sort(num);  
    for(int i=0;i<num.length-3;i++){  
      for(int j=i+1;j<num.length-2;j++){  
        int l=j+1;  
        int r=num.length-1;  
        while(l<r){  
          if(num[i]+num[j]+num[l]+num[r]==target){  
            List<Integer> temp=new ArrayList<Integer>();  
            temp.add(num[i]);  
            temp.add(num[j]);  
            temp.add(num[l]);  
            temp.add(num[r]);  
            res.add(temp);  
            while(l+1<r && num[l+1]==num[l]) l++;  
            l++;  
            while(l<r-1 && num[r-1]==num[r]) r--;  
            r--;  
          }  
          else if(num[i]+num[j]+num[l]+num[r]<target) l++;  
          else r--;  
        }  
        while(j+1<num.length-2 && num[j+1]==num[j]) j++;  
      }  
      while(i+1<num.length-3 && num[i+1]==num[i]) i++;  
    }  
    return res;  
   }  

16. 3Sum Closest Leetcode Java

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Solution:
Two pointers.
Similar to 3Sum
Now we need to check if the sum is closer target and update the res correspondingly. Also we can skip those element with same values if it has been processed.
Time complexity: O(n^2)

  public int threeSumClosest(int[] num, int target) {  
    if(num==null || num.length<3) return 0;  
    Arrays.sort(num);  
    int res=num[0]+num[1]+num[2];  
    for(int i=0;i<num.length-2;i++){  
      int l=i+1;  
      int r=num.length-1;  
      while(l<r){  
        int sum=num[i]+num[l]+num[r];  
        if(sum==target) return sum;  
        else if(sum<target) l++;  
        else r--;  
        if(Math.abs(sum-target)<Math.abs(res-target)) res=sum;  
      }  
      while(i<num.length-2 && num[i+1]==num[i]) i++;  
    }  
    return res;  
   }  

15. 3Sum Leetcode Java

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Solution:
Two pointers.
Sort the array, and use two pointers left and right to travel across the array and find the right numbers. Clearly if A[left]+A[right]<target, left++ which is the only way to get closer to target. Verse vise. In order to avoid duplicate triplets and save time, each time when we move the pointer, we move it to a new value different with the previous one. 
Time complexity: O(n^2)

 public List<List<Integer>> threeSum(int[] num) {  
    List<List<Integer>> res=new ArrayList<List<Integer>>();  
    if(num==null || num.length<3) return res;  
    Arrays.sort(num);  
    for(int i=0;i<num.length-2;i++){  
      int l=i+1;  
      int r=num.length-1;  
      while(l<r){  
        if(num[i]+num[l]+num[r]==0){  
          List<Integer> temp=new ArrayList<Integer>();  
          temp.add(num[i]);  
          temp.add(num[l]);  
          temp.add(num[r]);  
          res.add(temp);  
          while(l<r && num[l+1]==num[l]) l++;  
          l++;  
          while(l<r && num[r-1]==num[r]) r--;  
          r--;  
        }  
        else if(num[i]+num[l]+num[r]>0) r--;  
        else l++;  
      }  
      while(i<num.length-2 && num[i+1]==num[i]) i++;  
    }  
    return res;  
   }  

14. Longest Common Prefix Leetcode Java

Write a function to find the longest common prefix string amongst an array of strings.

Solution:
Use first String in the array as reference, compare all other arrays with it char by char. If any string has disagree char, return the current prefix, other wise add the processing char to the result common prefix.
Time complexity:O(m*n) m is Array Length, n is the prefix length.

 public String longestCommonPrefix(String[] strs) {  
    if(strs==null || strs.length==0) return "";  
    StringBuilder sb=new StringBuilder();  
    for(int i=0;i<strs[0].length();i++){  
      for(int j=1;j<strs.length;j++){  
        if(i>=strs[j].length()) return sb.toString();  
        if(strs[j].charAt(i)!=strs[0].charAt(i)) return sb.toString();  
      }  
      sb.append(strs[0].charAt(i));  
    }  
    return sb.toString();  
   }  

13. Roman to Integer Leetcode Java

Given a roman numeral, convert it to an integer.

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

Solution:

Process each char one time, for 'M','D','L','V' add the corresponding numbers. For'C','X','I' check the next char, if next char is corresponded with a larger number,add the current number, otherwise subtract it. For example the current char is 'I', if next one is 'V' or 'X', which means the current 'I' is part of 4 or 9, so we need to subtract 1 and then add 5, or 9 for next char.

 public int romanToInt(String s) {  
     if(s==null || s.length()==0) return 0;  
     int res=0;  
     for(int i=0;i<s.length();i++){  
       if(s.charAt(i)=='M') res+=1000;  
       else if(s.charAt(i)=='D') res+=500;  
       else if(s.charAt(i)=='C'){  
         if(i+1<s.length() && (s.charAt(i+1)=='D' || s.charAt(i+1)=='M')) res-=100;  
         else res+=100;  
       }  
       else if(s.charAt(i)=='L') res+=50;  
       else if(s.charAt(i)=='X'){  
         if(i+1<s.length() && (s.charAt(i+1)=='L' || s.charAt(i+1)=='C')) res-=10;  
         else res+=10;  
       }  
       else if(s.charAt(i)=='V') res+=5;  
       else if(s.charAt(i)=='I'){  
         if(i+1<s.length() && (s.charAt(i+1)=='V' || s.charAt(i+1)=='X')) res-=1;  
         else res+=1;  
       }  
       else return 0;  
     }  
     return res;  
   }  

12. Integer to Roman Leetcode Java

Given an integer, convert it to a roman numeral.

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

Solution:
The idea is straightforward. For each digit of the given number, find the corresponding roman letters.
3 cases:(a):1-3; (b): 4/9; (c) 5-8
I will provide two ways to process the number (1) from right-->left

 public String intToRoman(int num) {  
     String res="";  
     if(num==0) return res;  
     StringBuilder sb=new StringBuilder();  
     String[] rome={"I","V","X","L","C","D","M"};  
     int count=0;  
     while(num>0){  
       int dig=num%10;  
       count++;  
       if(dig==4 || dig==9){  
         sb.append((dig==4)? rome[2*count-1]:rome[2*count]);  
         sb.append(rome[2*count-2]);  
       }   
       else if(dig<5){  
         for(int i=0;i<dig;i++) sb.append(rome[2*count-2]);  
       }  
       else{  
         for(int i=0;i<dig-5;i++) sb.append(rome[2*count-2]);  
         sb.append(rome[2*count-1]);  
       }  
       num=num/10;  
     }  
     return sb.reverse().toString();  
   }  

(2) from left-->right

 public String intToRoman(int num) {  
    StringBuilder result= new StringBuilder();  
    char[] roman={'I','V','X','L','C','D','M'};  
    int div=1000;  
    int i=6;  
    while(div!=0){  
      int dig=num/div;  
      switch(dig){  
        case 9: result.append(roman[i]).append(roman[i+2]); break;  
        case 8: result.append(roman[i+1]).append(roman[i]).append(roman[i]).append(roman[i]); break;  
        case 7: result.append(roman[i+1]).append(roman[i]).append(roman[i]); break;  
        case 6: result.append(roman[i+1]).append(roman[i]); break;  
        case 5: result.append(roman[i+1]); break;  
        case 4: result.append(roman[i]).append(roman[i+1]); break;  
        case 3: result.append(roman[i]).append(roman[i]).append(roman[i]); break;  
        case 2: result.append(roman[i]).append(roman[i]); break;  
        case 1: result.append(roman[i]); break;  
        case 0: break;  
        default: break;  
      }  
      num=num%div;  
      div=div/10;  
      i=i-2;  
    }  
    return result.toString();  
   }  

11. Container With Most Water leetcode Java

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

Solution:

Two pointer and greedy

We maintain two pointer: left, right. if height[left]<height[right], move right pointer(right--) won't make the area bigger, because the height of the container is determined by shorter one. In this case area=height[left]*(right-left), move right pointer can only make height unchanged(height[new right]>=height[left]) or even shorter(height[new right]<height[left]). So in this case the only possible way to make the area bigger is move the left pointer(left++) and till the height is increased. Vice verse. 

The time complexity: O(n)

   public int maxArea(int[] height) {  
    if(height==null || height.length<2) return 0;  
    int l=0;  
    int r=height.length-1;  
    int maxA=(r-l)*Math.min(height[l],height[r]);  
    while(l<r){  
      if(height[r]<=height[l]) r--;  
      else l++;  
      maxA=Math.max(maxA,(r-l)*Math.min(height[l],height[r]));  
    }  
    return maxA;  
   }  

10. Regular Expression Matching Leetcode Java

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Solution:

1. Bruteforce 

(a) if p.charAt(j+1)!='*',if s.charAt(i)!=p.charAt(j) && p.charAt(j)) return false, 

else return (s,p,i+1,j+1); means if p.next char!='*', then it is simple, if s.charAt(i)!=p.charAt(j) && p.charAt(j) they are not matched.

(b) if p.charAt(j+1)=='*', we have to check all possible subMatch(i++,j+2) as long as s.charAt(i)==p.charAt(j) || p.charAt(j)=='.', if anyone of them return true, then s,p are matched. Because we don't know "*" represent exactly how many chars, we have to try each possibility.  For example, "abbbc" and "ab*bc", we have to check {"bbbc","bc"};{"bbc","bc"};{"bc","bc"}(matched return true); if no one return true, check the rest of string. 

Time complexity is very high, should be exponential level.

  public boolean isMatch(String s, String p) {  
    return subMatch(s,p,0,0);  
   }  
  public boolean subMatch(String s, String p, int i, int j){  
   if(j==p.length()) return (i==s.length());  
   if((j==p.length()-1)||(p.charAt(j+1)!='*')){  
    if((i==s.length())||((p.charAt(j)!='.')&&(s.charAt(i)!=p.charAt(j)))) return false;  
    else return subMatch(s,p,i+1,j+1);  
   }  
   else {  
     while ((i<s.length())&&((p.charAt(j)=='.')||(s.charAt(i)==p.charAt(j)))){  
       if(subMatch(s,p,i,j+2)) return true;  
       i++;  
      }  
       return subMatch(s,p,i,j+2);  
     }  
  }  

2. Dynamic Programing

We maintain an boolean matrix match[i][j], the matrix represent does s.substring(0,i+1) and p.substring(0,j+1) match. 

 The recurrence relation is :

(a) if p.charAt(j)!='*',if (s.charAt(i)==p.charAt(j)|| p.charAt(j)=='.') match[i+1][j+1]=match[i][j]

(b) else p.charAt(j)=='*' match[i+1][j+1]=match[i+1][j] ('*' represent one previous char) || match[i+1][j-1]('*'represent zero previous char) || (match[i][j+1] && (s.charAt(i)==p.charAt(j)|| p.charAt(j)=='.')('*' represent multiple previous char till the current i).

The advantage of dynamic programming is previous information is stored and no need to recalculate. 

A little trick of this is set the size of match to be [ls+1][lp+1] and set match[0][0]=true. Update match[0][j] when j is iterating. The trick allow us to process the corner case much easier. For example "" and "a*b*" ,match[0][4]=match[0][2]=match[0][0]=true;  

Time complexity: O(m*n)

   if(s==null || p==null) return false;  
    int ls=s.length();  
    int lp=p.length();  
    boolean[][] match=new boolean[ls+1][lp+1];  
    match[0][0]=true;  
    for(int i=-1;i<ls;i++){  
      for(int j=0;j<lp;j++){  
        if(i==-1) match[0][j+1]=j>0 && p.charAt(j)=='*' && match[0][j-1];  
        else{  
        if(s.charAt(i)==p.charAt(j) || p.charAt(j)=='.') match[i+1][j+1]=match[i][j];  
        else if(p.charAt(j)=='*'){  
           match[i+1][j+1] =match[i+1][j-1]||match[i+1][j]||(match[i][j+1] && (s.charAt(i)==p.charAt(j-1) ||p.charAt(j-1)=='.'));  
        }  
        else match[i+1][j+1]=false;  
        }  
      }  
      }  
    return match[ls][lp];  
   }  

9. Palindrome Number Leetcode Java

Determine whether an integer is a palindrome. Do this without extra space.

Solution:
1. Use the reverse Integer to reverse it and check if they are equal. If it overflows during the revers, then it is not a palindrome number. I am not going to provide the code, please refer to reverse Integer.

2.compare the leftmost digit with rightmost digit one by one till the two meets. Calculating rightmost digit is easy just mod 10, while calculating leftmost digit is more advanced. First find the biggest dividend of the number and leftmost digit will be the number divided by the dividend.

    public boolean isPalindrome(int x) {  
     if(x<0) return false;   
     if(x<10) return true;  
     int div=10;  
     while(x/div>=10) div*=10;  
     while(div>0){  
       int l=x/div;  
       int r=x%10;  
       if(l!=r) return false;  
       x=x-l*div;  
       div=div/100;  
       x=x/10;  
     }  
     return true;  
   }  

8. String to Integer (atoi) Leetcode Java

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Solution:

Just like reverse Integer, the algorithm is not hard, have to be very careful and take care of all possible cases. My solution contains 4 parts. 1st: Discard all upfront whitespaces. 2nd, determine the sign of number. 3rd: process the number and ignore non-numerical char after that. 4th. During the conversion, take care of overflow. Just like reverse Integer, this check: Integer.MAX_VALUE-y%10)/10<res return (pos)? Integer.MAX_VALUE : Integer.MIN_VALUE; is necessary and enough to test all the overflow, 2137385647, -2147483647, 2137385648(return 2137385647) and -2147483648 will all return the right answers. 

    public int atoi(String str) {  
    if(str==null || str.length()==0) return 0;  
    int start=0;  
    int res=0;  
    boolean pos=true;  
    while(start<str.length() && str.charAt(start)==' ') start++;  
    if(start==str.length()) return 0;  
    if(str.charAt(start)=='+'||str.charAt(start)=='-') {  
      pos=str.charAt(start++)=='+';  
   }  
   for(int i=start;i<str.length() && str.charAt(i)<='9'&&str.charAt(i)>='0';i++){  
     int dig=str.charAt(i)-'0';  
     if((Integer.MAX_VALUE-dig)/10<res) return (pos)? Integer.MAX_VALUE : Integer.MIN_VALUE;  
     res=res*10+dig;  
   }  
   return (pos)? res : -res;  
   }  

7. Reverse Integer Leetcode Java

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Solution:

The algorithm is not difficult.Just reverse digit of the integer one by one. The tricky part is to detect the possible overflow when we reverse the integer. First, we take the absolute value of x to make reversing easier and code cleaner. Because we use multiplication and addition to reverse the integer. For detecting the overflow, we test if next possible operation would overflow before we do it. So we check if Integer.MAX_VALUE-y%10)/10<res if yes, then return MIN_VALUE or MAX_VALUE depends on its original sign. We don't have to worry about the MIN_VALUE, because Integer.MAX_VALUE =  2147483647 and Integer.MIN_VALUE= -2147483648, so if x=2137385647 or -2147483647 (although this corner case is not possible in this problem), (Integer.MAX_VALUE-y%10)/10<res) is not true, and it won't return 0; The Integer.MIN_VALUE has to be considered before Math.abs(). 

   

   public int reverse(int x) {  
    int res=0;  
    boolean pos=x>0;  
    if(x==Integer.MIN_VALUE) return 0;  
    int y=Math.abs(x);  
    while(y!=0){  
      if((Integer.MAX_VALUE-y%10)/10<res) return 0;  
      else res=res*10+y%10;  
      y=y/10;  
    }  
    return (pos)? res : -res;  
   }  

6. ZigZag Conversion Leetcode Java

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Solution:
This problem is straightforward and it test our string processing ability and logical thinking. For the first row and last row, we only need to add zig chars, for the middle rows, we need to add both zig and zag chars. Zig char index: j and next one is j+2*(nRows-1));zag char index: j+2*(nRows-i-1)) . For instance, the second row of giving example, j=1, A: 1, P:1+2*(3-1-1)=3, L: 1+2*(3-1)=5, S: 5+2*(3-1-1)=7.... 
The time complexity is: O(n) because each char is only visited once. 

  public String convert(String s, int nRows) {  
    if(s==null || s.length()==0 || nRows<=1 || s.length()<=nRows) return s;  
    StringBuilder sb=new StringBuilder();  
    for(int i=0;i<nRows;i++){  
      int j=i;  
      while(j<s.length()){  
        sb.append(s.charAt(j));  
        if(i!=0 && i!=nRows-1 && (j+2*(nRows-i-1))<s.length()) sb.append(s.charAt(j+2*(nRows-i-1)));  
        j=j+2*(nRows-1);  
      }  
    }  
    return sb.toString();  
   }