Two Sum

When I first saw this question, it seems to take O(n^2) if a normal algorithm was used. However, try to take use of HashMap to store index and check whether what you want is in the array. Totally the following algorithm just need O(n) time

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
     
        HashMap<Integer,Integer> numIdxMap = new HashMap<Integer,Integer>();
        // Pre-process
        for(int i = 0; i < numbers.length; i ++){
            int remain = target - numbers[i];
                numIdxMap.put(remain,i);
        }
        int[] result = new int[2];
        for(int i = 0; i < numbers.length; i++){
            int num = numbers[i];
            if(numIdxMap.containsKey(num)){
                int idx = numIdxMap.get(num);
                if((num*2) == target && idx == i){
                    continue;                
                }
                else{
                    if(idx > i){
                        result[0] = i+1;
                        result[1] = idx+1;
                    }
                    else{
                        result[0] = idx+1;
                        result[1] = i+1;
                    }
                    break;
                 
                }
            }
        }
        return result;
    }
}

Swap Nodes in Pairs

This question is a very fundamental one about manipulation of linked lists.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode preHead = new ListNode(0);
        preHead.next = head;
        ListNode preNode = head;
        ListNode pstNode = head.next;
        //swap first two
        preHead.next = pstNode;
        preNode.next = pstNode.next;
        pstNode.next = preNode;
        while(preNode.next!=null && preNode.next.next != null){
            ListNode tmpPre = preNode;
            preNode = preNode.next;
            pstNode = preNode.next;
         
            //swap
            tmpPre.next = pstNode;
            preNode.next = pstNode.next;
            pstNode.next = preNode;
        }
        return preHead.next;
    }
}

Binary Tree Inorder Traversal (Iterately)

Not hard question. Basic idea is to use stack. Stack is a good tool for replacing loop with recursion. One thing should be aware of is "Be careful for different cases"

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
     
        ArrayList<Integer> rslt = new ArrayList<Integer>();
        if(root == null) return rslt;
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
     
        TreeNode tmpRoot = root;
        stack.push(tmpRoot);
        while(!stack.isEmpty()){
            while(tmpRoot.left != null){
                stack.push(tmpRoot.left);
                tmpRoot = tmpRoot.left;
            }
         
            TreeNode tmpNode = stack.pop();
         
            rslt.add(tmpNode.val);
            if(tmpNode.right != null){
                tmpRoot = tmpNode.right;
                stack.push(tmpRoot);
            }
            else{
                if(stack.isEmpty()) break;
                else{
                    tmpRoot = stack.peekFirst();
                    tmpRoot.left = null;
                }
            }
        }
        return rslt;
    }
}

Interleaving String

This problem really took me too much time. I tried recursion and loop methods, but both get TLE. What I initially thought was that: usually we may meet 4 cases: 1) kth char of s3 is same as ith of s1, while not as jth of s2;2) kth char of s3 is same as jth of s2, while not as ith of s1; 3)  kth char of s3 is same as ith of s1, also same as jth of s2; 4)  kth char of s3 is NOT as same as ith of s1, neither jth of s2. Deal with above 4 cases differently, then we can do our job. But this idea always run out of time.

After taking a look at others' code in Leecode community, I finally realized that this should be solved using DP, like knapsack problem, and thanks to  qingjinlyc for his clear explanation. 

Now, let me just explain a little bit. 

One thing we need to be clear about is rslt[i][j] indicates whether s3.substring(0,i+j) is interleaving string of s1.substring(0,i) and s2.substring(0,j). In other words, to determine whether s3.substring(0,i+j) can be interleaving of s1.substring(0,i) and s2.substring(0,j), we need to find a "true" way from (0,0) of matrix to (i,j). Now lets simplify this problem into the smallest one. Assume I want to know whether (i,j) is true, how can I get the answer? I will take a look at left side and above side of (i,j), i.e. (i-1,j) and (i, j -1). If (i-1,j) is true and s3.charAt(i+j-1) == s1.charAt(i-1) (Be careful here, i and j starts from 1, so we need to minus 1), then this could be a valid "true way" to (i,j), similar case with s2. So we can solve this problem in this way.
 

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() != 0 && s2.length() != 0 && (s1.length()+s2.length() != s3.length())) return false;
        if (s1.length() != 0 && s2.length() == 0){
            if(s1.equals(s3)) return true;
            else return false;
        }
        if (s1.length() == 0 && s2.length() != 0){
            if(s2.equals(s3)) return true;
            else return false;
        }
        if(s1.length() == 0 && s2.length() == 0){
            if(s3.length() == 0) return true;
            else return false;
        }

        boolean[][] rslt = new boolean[s1.length()+1][s2.length()+1];
        rslt[0][0] = true;
        for(int i = 1; i<=s1.length();i++){
            rslt[i][0] = s1.substring(0,i).equals(s3.substring(0,i)) ;
        }
        for(int j = 1; j<=s2.length();j++){
            rslt[0][j] = s2.substring(0,j).equals(s3.substring(0,j));
        }
     
        for(int i= 1;i <=s1.length();i++){
            for(int j = 1; j<=s2.length();j++){
                rslt[i][j] = ((s3.charAt(i+j-1)==s1.charAt(i-1) && rslt[i-1][j]) ||
                (s3.charAt(i+j-1)==s2.charAt(j-1) && rslt[i][j-1]));
            }
        }
        return rslt[s1.length()][s2.length()];
 
    }
 
}

Remove Duplicates from Sorted List II

Not a quite difficult question. The idea is based on first version of "Remove Duplicates from Sorted List".

Firstly, remove duplicate nodes from list, at the same time, set dplcFlag to be true, which means that duplicate nodes exist now. Next time when a node with different value is met, remove the preNode.

In the following code, preHead is a fake head node before this list, which is very useful when we have cases like "1-1-1-1-2-2-2-3-4".

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode preNode = head;
        ListNode preHead = new ListNode(0);
        preHead.next = preNode;
        ListNode tmpHead = preHead;
        ListNode crntNode = preNode.next;
        boolean dplcFlag = false;
        while(crntNode !=null){
            if(preNode.val == crntNode.val){
                preNode.next = crntNode.next;
                crntNode.next = null;
                crntNode = preNode.next;
                dplcFlag = true;
            }else{
                if(dplcFlag){
                    tmpHead.next = crntNode;
                    preNode.next = null;
                    preNode = crntNode;
                    crntNode = crntNode.next;
                    dplcFlag = false;
                }
                else{
                    tmpHead = preNode;
                    preNode = crntNode;
                    crntNode = crntNode.next;
                }
            }

        }
        if(dplcFlag)
            tmpHead.next = crntNode;
            preNode.next = null;
            preNode = crntNode;
        }
     
        return preHead.next;
    }
}

Valid Palindrome

This question is quite easy I believe. First step I take is to pre-process the string, eliminate characters except alphanumerical ones. Method prc is responsible for this work.

public class Solution {
    public boolean isPalindrome(String s) {
        if(s == null) return true;
        String lowCase = s.toLowerCase();
        String prcdS = prc(lowCase);
        if(prcdS.length() < 2) return true;
        int i = 0;
        int j = prcdS.length() - 1;
       
        while(i<j){// check whether the processed string is palindrome
            if(prcdS.charAt(i) != prcdS.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
   
    public String prc(String s){
        StringBuffer result = new StringBuffer();
        for(int i = 0; i < s.length(); i ++){
            if((s.charAt(i) >= 'a' && s.charAt(i) <= 'z')||(s.charAt(i) >= '0' && s.charAt(i) <= '9')) result.append(s.charAt(i));
        }
       
        return result.toString();
    }
}

Gas Station

This is a quite easy question. Actually, instead of "easy", I would rather say "smart". At first, you may wanna say just test each index, if a tour around the "circuit" can be complete, then return this index. Yes, this is not wrong. However, this might take too much time.  So, lets start from these potential sites, where gas[i] >= cost[i], so the car with empty tank can have enough gas to go to next station. Then, start from one of them, for instance site i, keep checking if car can go to j station, with total sum of gas is non-negative, if sum is smaller than 0 at site k, it means that starting from the index i is not a good choice. In this case, we need to find another potential site after k. Why not start over from i+1? Good question. For example, if we start from one site h between i and k, and gas[h] >= cost[h]. As we know, before arriving at h, sum must be larger than or equal to 0, even if this, sum get < 0 at site k. So if start from site h, sum definitely will get < 0. Thus it is useless to start from any sites between i and k, even if they are potential. So over and over again, we continue our process, until we find the index we want, or meet the end of array. If end was met, it means no suitable index has been found, return -1.

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if(gas == null || cost == null) return -1;
       
        for(int i = 0; i < gas.length; ){
            if (gas[i] >= cost[i]){
                int tmpIdx = startTest(gas, cost,i);
                if (tmpIdx == i) return i;// car can go back to i , i.e. i is what we want
                else{
                    if(tmpIdx == -1) return -1;
                    else{
                        if(tmpIdx!= i)
                        i = tmpIdx;
                    }              
                }
            }
            else{
                i++;
            }
        }
       
        return -1;
    }
   
    public int startTest(int[] gas, int[] cost,int startIdx){
        int length = gas.length;
        int sum = gas[startIdx] - cost[startIdx];
        int i = startIdx + 1;
        i = i%length;
       
        while(i!=startIdx){
           
            sum += gas[i] - cost[i];
            if(sum < 0) break;// can't arrive at site i+1, or station i+1
            i++;
            i = i%length;
        }  
        if(sum < 0){// if failed
            i++;
            // i = i%length;
            while(i < length && i != startIdx){// find next potential index after i, where test failed
                if(gas[i] >= cost[i]) return i;
                else{
                    i++;
                    // i = i%length;                  
                }
            }
            // if can not find another potential index, then it is
            // not possible to complete the circuit
            return -1;
        }
        else return startIdx;
    }
}

Add Two Numbers

Simple question I believe. Just a few cases we need to be aware of: 1) l1 and l2 are NOT always of the same length; 2) for cases like {1}, {9} we need to add a new digit, or node even l1 and l2 are both null.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        int addOne = 0;
        ListNode newHead = null;
        ListNode tmpNode = null;
        while(l1!=null && l2!=null){
            int sum = l1.val + l2.val + addOne;
            int val = sum%10;
            if(sum > 9) addOne = 1;
            else addOne = 0;
            if(newHead == null){
                newHead = new ListNode(val);
                tmpNode = newHead;
            }
            else{
                ListNode node = new ListNode(val);
                tmpNode.next = node;
                tmpNode = tmpNode.next;
            }
         
            l1 = l1.next;
            l2 = l2.next;
        }
     
        if(l1 == null && l2!=null){
            while(l2!=null){
                int sum = l2.val + addOne;
                int val = sum%10;
                if(sum > 9) addOne = 1;
                else addOne = 0;
                ListNode node = new ListNode(val);
                tmpNode.next = node;
                tmpNode = tmpNode.next;
                l2 = l2.next;
            }
         
        }else{
            if(l1!= null ){
                while(l1!=null){
                    int sum = l1.val + addOne;
                    int val = sum%10;
                    if(sum > 9) addOne = 1;
                    else addOne = 0;
                    ListNode node = new ListNode(val);
                    tmpNode.next = node;
                    tmpNode = tmpNode.next;
                    l1 = l1.next;
                }
            }
        }
        if(addOne == 1) {// inspired by case {1}, {9,9}
            ListNode node = new ListNode(addOne);
            tmpNode.next = node;
            tmpNode = tmpNode.next;                  
        }
        return newHead;
    }
}

Insertion Sort List

I wrote 2 solutions for this problem. Solution 1 can get correct result, but TLE. I am not sure why this happens. Since time complexity of the code is O(n^2),  it is supposed to be easier to pass test cases. One guy said TLE might be due to that algorithm generates circular list, but I can not agree with him, because each time a node is inserted or moved, the next of node is definitely "pointed" to some certain node.

Solution 2 is accepted. The only difference is that solution 2 creates a different list, not manipulates with original list.

Now based on my experience solving Leetcode problems, I think sometimes Leetcode OJ does not fully check all the restrictions described in question. Some fake answers might get accepted as well. Thus the AC rate might not be a good criteria to determine this question is difficult or not.

Alright, lets check the code out.
//Solution 1, but TLE
public ListNode insertionSortList(ListNode head) {
     
        if(head == null || head.next == null) return head;
     
        ListNode crntPre = head;
        ListNode crntNode = crntPre.next;
        // make sure that first 2 elements are sorted    
        if(crntPre.val > crntNode.val){//i.e. swap head and head.next
            crntPre.next = crntNode.next;
            crntNode.next = crntPre;
            head = crntNode;
        }
        crntPre = crntNode;
        crntNode = crntNode.next;
        while(crntNode != null){
            ListNode tmpNode = head;
            ListNode tmpPre = null;
            while(tmpNode != crntNode && crntNode.val >= tmpNode.val ){
                tmpPre = tmpNode;
                tmpNode = tmpNode.next;
            }
         
            if(tmpPre == null){// crntNode.val < head.val
                crntPre.next = crntNode.next;
                crntNode.next = head;
                head = crntNode;              
            }
            else{

                if(crntNode.val < tmpNode.val){// crntNode.val < tmpNode.val, insert crntNode before tmpNode
                    crntPre.next = crntNode.next;
                    crntNode.next = tmpNode;
                    tmpPre.next = crntNode;
                 
                }
                //else, crntNode.val is larger than all nodes before it, no need for any change
            }
            crntPre = crntNode;
            crntNode = crntNode.next;
        }
     
        return head;
}


// Solution 2, accpeted

public ListNode insertionSortList(ListNode head) {
        // Solution 2
        if(head == null || head.next == null) return head;
     
        ListNode newHead = new ListNode(head.val);
     
        ListNode crntNode = head.next;

        while(crntNode != null){
             
            ListNode tmpNode = newHead;
            ListNode tmpPre = null;
            ListNode newNode = new ListNode(crntNode.val);
         
            while(tmpNode!=null && tmpNode.val <= crntNode.val){// any differecen between < and <= ??
                tmpPre = tmpNode;
                tmpNode = tmpNode.next;
            }
            if(tmpPre == null){// smaller than newHead
             
                newNode.next = newHead;
                newHead = newNode;
            }
            else{
                if(tmpNode == null){// crntNode.val is larger than all nodes of newHead
                    tmpPre.next = newNode;
                }
                else{
                    newNode.next = tmpNode;
                    tmpPre.next = newNode;
                }
            }
         
            crntNode = crntNode.next;
        }
     
        return newHead;
    }
}

Reorder List

I solved one similar question before. That question is about reverse linked list, which is more difficult than this one. So this question does not take me much time. But at first, as I just want to test whether OJ system has restriction about time complexity on this problem, I did not use stack to store these nodes to be reordered. Instead, just use a loop to find the node, after which a new node should be inserted. No doubt, TLE, lol. Thus a stack is used. Sacrifice space for time. WAIT! The problem requires "in-place". Alright, solution 1 is NOT "in-place", while solution 2 is.

Solution 1 is quite straightforward, insert top element of stack after tmpPre node. Iterate above process until stack is empty. However, this solution needs extra space, i.e. O(n) space for stack. In solution 2, stack is abandoned.
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

// Solution 1
public class Solution {
    // Solution 1
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null) return;
        // Now the linked list is at least of length 3
        ListNode slow = head;
        ListNode fast = head;
     
        while(fast != null && fast.next != null ){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode copySlow = slow.next;
        LinkedList<ListNode> stack = new LinkedList<ListNode>();
        while(copySlow != null){// Use stack to store the nodes after slow, which will be inserted into the first //half of list
            stack.push(copySlow);
            copySlow = copySlow.next;
        }
        slow.next = null;
        ListNode tmpPre = head;
        while(!stack.isEmpty()){
            ListNode tmpNode = stack.pop();
            tmpNode.next = tmpPre.next;
            tmpPre.next = tmpNode;
            tmpPre = tmpPre.next.next;
        }
    }
}

For solution 2, at first, I have no idea how to deal with this question "in-place". After today's workout, I suddenly think of DFS while taking a shower. DFS can be implemented in 2 ways, recursively, or using a stack. This gives me the answer about how to solve this problem, yes, recursion! Start the recursion from node slow until we meet the end of list, then move end of the list after node tmpHead.  After each movement, tmpHead goes to the node right behind the newly inserted node, i.e. tmpHead = tmpHead.next.next .

One thing to notice is that if you want to keep the change of one passed-in object, like tmpHead here in one method, DO NOT make it void, make it the type of this object, and return that object as method finished.

//Solution 2

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        //Solution 2
        if(head == null || head.next == null || head.next.next == null) return;
        // Now the linked list is at least of length 3
        ListNode slow = head;
        ListNode fast = head;
     
        while(fast != null && fast.next != null ){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode preHalfHead = slow;
        ListNode tmpHead = head;
     
        // recursively insert the list node into first half of list
     
         reorderList(tmpHead, preHalfHead);
    }
 
    public ListNode reorderList(ListNode tmpHead, ListNode currentNode){
    if(currentNode.next == null) return tmpHead;
        tmpHead= reorderList(tmpHead,currentNode.next);
     
//        if(currentNode.next.next == null){
            currentNode.next.next = tmpHead.next;
            tmpHead.next = currentNode.next;
            currentNode.next = null;
         
            tmpHead= tmpHead.next.next;
            return tmpHead;
//        }
    }
}

Minimum Window Substring

Code is shown as below. One thing I really need to notice is the mistake I made about HashMap. or more generally, the Collections of Java. When I was using .get() method, I think HashMap.get(i) is same as a variable. However, this opinion is totally wrong! If you need to change the value of HashMap.get(i), please use another variable var to store HashMap.get(i), change value of var, and put it back, i.e. HashMap.put(i,var)

public class Solution {
    public String minWindow(String S, String T) {
        if(S == null || T == null || S.length() < T.length()) return "";
       
        int SLen = S.length();
        int TLen = T.length();
       
        if(SLen == TLen ) {
            if(T.equals(S)) return S;
            // else return ""; // be careful, content might be the same, but order is different
        }
        // charAndIdx  stores the index of element of T in S
        LinkedList<DT> charAndIdx = new LinkedList<DT>();
        HashMap<Character, Integer> TMap = new HashMap<Character, Integer>();
     
        initialHM(TMap, T); // TMap is used to store the elements of T, and how many times they appear
     // However, when used in following loop, TMap stores num of crntC in T - num of crntC in charAndIdx
        int count = 0;// count is used to count the number of valid or useful elements contained in charAndIdx
        String result = null;
        for(int i = 0; i < SLen;i ++){
            char crntC = S.charAt(i);
            if(TMap.containsKey(crntC)){
                if(TLen == 1) return T;
                if(TMap.get(crntC) > 0) count ++;
                int t = TMap.get(crntC);// record how many times crntC appear until one valid window is found
                TMap.put(crntC,t - 1);
                DT dt = new DT(crntC,i);
                charAndIdx.add(dt);
               
                if(count == TLen){// one valid window is found
                   
                    DT head = charAndIdx.removeFirst();
                    int k = TMap.get(head.c);
                    TMap.put(head.c,k+1);
                    DT tail = charAndIdx.peekLast();
                    String tmpResult;
                    while(TMap.get(head.c) < 1){// If the head.c appear more than once in the valid substring
// if TMap.get(head.c) is 0, then it means all the head.c has or have been contained in the charAndIdx.
// If  TMap.get(head.c) > = 1, we should move on to find next index i where more head.c can be found, so
// that the charAndIdx contains all the letters of T, i.e. we need to get out of this while loop, and then i++
                        head = charAndIdx.removeFirst();
                        int m = TMap.get(head.c);
                        TMap.put(head.c,m+1);
                       
                    }//In this while loop, what I want is to remove one element of T, then charAndIdx should just //lack this element. This loop actually help us remove redundant elements found in charAndIdx list.  
  
                        tmpResult = S.substring(head.index,tail.index + 1);
                       
                        if (tmpResult.length() == TLen) return tmpResult;
                        if (result == null || tmpResult.length() < result.length()) result = tmpResult;
                    count --;
                }
            }
           
        }
        if(result == null) return "";
        return result;
    }
   
    public void initialHM(HashMap<Character, Integer> TMap ,String T){
        for(int i = 0; i < T.length();i++){
            if(TMap.containsKey(T.charAt(i))) {
                int j = TMap.get(T.charAt(i));
                TMap.put(T.charAt(i),j + 1);
            }
            else TMap.put(T.charAt(i),1);
        }
    }
   
}

class DT{
    public char c;
    public int index;
    DT(char x, int y){
        c = x;
        index = y;
    }
}

Longest Valid Parentheses

Let us have a talk about this problem today. Since in description of this question , definition of "valid(well-formed) " is not very clear, my first submission gave wrong answer. From the test case I failed, I know that cases like "(())" is also considered as valid. After understanding the definition, we can get started.

In my algorithm, firstly, ')'s at beginning of String s are definitely supposed to be ignored, because there is no '(' before them, not possible to form valid parentheses. So we just need to find the first '(' in s. Then I put index of each '(' into a stack(actually implemented by LinkedList), as s is traversed in while loop. If ')' is founded, then it can form a valid parentheses with top element of stack, only when s is not empty( if empty, it means that we have met more ')'s than '(' so far, not possible for this ')' to form valid parentheses), pop out the top, then store indexes of both into a ArrayList in Solution 2(in Solution 1, HashMap, I will talk about the difference later). Now it's time for the key step, merge! We need to merge the new added parentheses with saved ones stored. For case like "()()", when we arrive at index 3, we should know that pair of (0,1) has been stored, and (2,3) is newly added, at this moment, these 2 pairs can be combined together to get a new valid parentheses (0,3). Condition here is that right index of old pair is next to left index of new one. I call this "concatenate". Another special case we need to consider is "(())". If we get to index 3, we can know that (1,2) has been stored, and (0,3) is newly added. We can see that (0,3) just includes (1,2), i.e. 1-0 == 3-2. This is also a condition we should take into account, where merge could happen.

In one iteration, the max time needed for merge is O(i), thus the worst case for finishing this algorithm takes O(n^2) time.

Iterate above process until end of String s is met. Then find the longest valid parentheses stored in the ArrayList. Return the length. (Only takes O(n) time)

Now, what is difference between Solution 1 and 2? HashMap and ArrayList. At first, I chose HashMap, since I store left and right index of parentheses directly, left as key, right as value. However, order of traversal of HashMap is not clear to us. And newly added element is only possible to merge with previously added one. Thus if HashMap is applied, it might take longer time to find the parentheses to merge with the new one. So ArrayList is used. We can start from the end of ArrayList, if the end is not what we need, just break the while loop in merge.

Actually, Solution 1 should return correct result as Solution 2 does. But 1 failed due to TLE!

public class Solution {// case ()((())()
    // Solution 1
    //  public int longestValidParentheses(String s) {
    //     if(s == null || s.length() < 2) return 0;
    //     int longestLen = 0;    
    //     int i = 0;
       
    //     while(i < s.length() && s.charAt(i) == ')'){// find 1st '(' in s
    //         i++;
    //     }
    //     if(i == s.length()) return 0;
    //     LinkedList<Integer> leftList = new LinkedList<Integer>();// store index of left parentheses
    //     HashMap<Integer, Integer> hmLeftRightIdx = new HashMap<Integer, Integer>();// store indexes of //left, right parentheses which are valid
    //     //int leftIdx = -1;
    //     while(i < s.length()){
    //         if(s.charAt(i) == '('){// if '(', we should wait to see what will happen next
    //             leftList.push(i);
    //         }
    //         else{// current char is ')', it is possible to find valid pairs, depending on some conditions
    //             if(!leftList.isEmpty()){// if empty, more ')' exist from index 0 to index i
    //                 int leftIdx = leftList.pop();
    //                 hmLeftRightIdx.put(leftIdx,i);
    //                 merge(hmLeftRightIdx,leftIdx);
    //             }
    //         }
    //         i++;
    //     }
    //     if(hmLeftRightIdx.isEmpty()) return 0;
       
    //     for(Integer index:hmLeftRightIdx.keySet()){
    //         int len = hmLeftRightIdx.get(index) - index + 1;
    //         if(len>longestLen) longestLen = len;  
    //     }
       
    //     return longestLen;
    // }
    // public void merge(HashMap<Integer, Integer> hmLeftRightIdx, int leftIdx){
    // if (hmLeftRightIdx.size() < 2 || !hmLeftRightIdx.containsKey(leftIdx)) return;
    //                 int rightIdx = hmLeftRightIdx.get(leftIdx);
    //                 boolean addedFlag = false;
    //                 int idxMerge= -1;
    //                 for(Integer index:hmLeftRightIdx.keySet()){
    //                 if(index != leftIdx){
    //                 if((leftIdx - hmLeftRightIdx.get(index)) == 1
    //                 ||((index - leftIdx) == (rightIdx - hmLeftRightIdx.get(index)) )){//2 '(' close to //each other, merge them, store smaller index and new length
    //                 addedFlag = true;
    //                 idxMerge = index;
    //                 break;
    //                 }
    //                 }
    //                 }
    //                 if(addedFlag && (leftIdx - hmLeftRightIdx.get(idxMerge)) == 1){// concatenate
    //                     int newRight = hmLeftRightIdx.get(leftIdx);
    //                     hmLeftRightIdx.remove(leftIdx);
    //                     hmLeftRightIdx.put(idxMerge,newRight);
    //                     merge(hmLeftRightIdx,idxMerge);
    //                 }
                   
    //                 else{// include or cover
    //                     if(addedFlag){
    //                         hmLeftRightIdx.remove(idxMerge);
    //                         merge(hmLeftRightIdx,leftIdx);
    //                     }
    //                 }                  
    // }

    // Solution 2:
    public int longestValidParentheses(String s) {
        if(s == null || s.length() < 2) return 0;
        int longestLen = 0;    
        int i = 0;
       
        while(i < s.length() && s.charAt(i) == ')'){// find 1st '(' in s
            i++;
        }
        if(i == s.length()) return 0;
        LinkedList<Integer> leftList = new LinkedList<Integer>();
        ArrayList<DT> arrLeftRightIdx = new ArrayList<DT>();
        while(i<s.length()){
            if(s.charAt(i) == '('){// if '(', we should wait to see what will happen next
                leftList.push(i);
            }
            else{// current char is ')', it is possible to find valid pairs, depending on some conditions
                if(!leftList.isEmpty()){// if empty, more ')' exist from index 0 to index i
                    int leftIdx = leftList.pop();
                    DT dt = new DT(leftIdx,i);
                    arrLeftRightIdx.add(dt);
                    merge(arrLeftRightIdx);
                }
            }
            i++;          
        }
       
      for(DT dt:arrLeftRightIdx){
      int len = dt.right - dt.left + 1;
      if(len>longestLen) longestLen = len;  
  }
       
        return longestLen;
    }
   
    public void merge(ArrayList<DT> arrLeftRightIdx){
        if(arrLeftRightIdx.size()<2) return;
        int i = arrLeftRightIdx.size() - 1;
       
        while( i >= 1 &&( ((arrLeftRightIdx.get(i).left - arrLeftRightIdx.get(i-1).right) == 1) ||((arrLeftRightIdx.get(i-1).left - arrLeftRightIdx.get(i).left)==(arrLeftRightIdx.get(i).right-arrLeftRightIdx.get(i-1).right)))){
            if((arrLeftRightIdx.get(i).left - arrLeftRightIdx.get(i-1).right) == 1){// concatenate
                int newRight = arrLeftRightIdx.get(i).right;
                int newLeft = arrLeftRightIdx.get(i-1).left;
                arrLeftRightIdx.remove(i);
                arrLeftRightIdx.remove(i-1);
                DT dt = new DT(newLeft,newRight);
                arrLeftRightIdx.add(dt);
            }
            else{// include
                arrLeftRightIdx.remove(i-1);
            }
            i--;
        }
    }
}

class DT{
    public int left;
    public int right;
    DT(int x, int y){left = x; right = y;}
}

Decode Ways

Please check comments below for understanding the code. Any questions? Please let me know.

public class Solution {
    public int numDecodings(String s) {// if step is 1, only 1 or 0 way to decode, depending on whether the char is '0', if step is 2
        if (s == null) return 0;
        if (s.equals("") || s.equals("0")) return 0;
        if (s.length() < 2) return 1;
        HashMap<Integer,Integer> record = new HashMap<Integer,Integer>();
        // record is used to store num of decodings corresponding to the index, so DP is applied
        int result = numDecode(s,0,record);
        return result;
    }
    // numDecode is used to compute the number of decoding ways from startIdx of String s.
    // for this question, since at most we get '26' for each letter, we only need to care about current and next       // char, i.e. 2 digits. One thing we should know is that when we take one way(a few steps) from startIdx,
      // then  go through all chars in s, then this way can be considered as successful, or valid. If startIdx finally    // gets larger than or equal to s.length() - 1, we should return 1, except that the last digit or char of s is 0, in           // which case 0 is returned, since only '10' or '20' is valid case
    public int numDecode(String s, int startIdx, HashMap<Integer,Integer> record){
        if(record.containsKey(startIdx)) return record.get(startIdx);
     
        if(startIdx > s.length() - 1){
            record.put(startIdx,1);
            return 1;
        }
        if(startIdx <= s.length() - 1 && s.charAt(startIdx) == '0') {// case s.charAt(startIdx) == '0' return 0
            record.put(startIdx,0);
            return 0;
        }else{
            if(startIdx == s.length() - 1){
                record.put(startIdx,1);
                return 1;              
            }
        }
        int count;
        if((s.charAt(startIdx)-'2' )>0) {// if it is '3' or larger, only take step as 1 to decode it, go to next index
            count = numDecode(s,startIdx+1,record);
            record.put(startIdx,count);
            return count;
        }
        else{
            if((s.charAt(startIdx)-'1' ) == 0) {// if is '1', both step 1 or 2 is okay, for '10'                                                                                               //numDecode(s,startIdx+2,record) return 1,
                                                          //numDecode(s,startIdx+1,record) return 0, sum is 1, correct
                count = numDecode(s,startIdx+1,record) + numDecode(s,startIdx+2,record);
                record.put(startIdx,count);
                return count;
            }
            else {// in this case s.charAt(startIdx) == 2
               if((s.charAt(startIdx + 1) - '6') <= 0){//smaller than or equal to '26', both step 1 or 2 okay, for '20'                                                              //numDecode(s,startIdx+2,record) return 1,
                                                          //numDecode(s,startIdx+1,record) return 0, sum is 1, correct
                    count = numDecode(s,startIdx+1,record) + numDecode(s,startIdx+2,record);
                    record.put(startIdx,count);
                    return count;
                }
                else {// larger than '26', only step 1 method can be used
                    count = numDecode(s,startIdx+1,record);
                    record.put(startIdx,count);
                    return count;
                }
            }
        }
    }
}

Remove Duplicates from Sorted List

This problem is quite easy. Use a current node and a node just before it to traverse this linked list, compare the value of current node with preNode, if same, delete current node, otherwise, move both to next one.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
     
        ListNode preNode = head;
        int value = preNode.val;
        ListNode currentNode = head.next;
        while(currentNode !=null ){
         
            if(value == currentNode.val){
                preNode.next = currentNode.next;
                currentNode.next = null;
                currentNode = preNode.next;
            }
         
            else{
                preNode = preNode.next;
                currentNode = currentNode.next;
                value = preNode.val;
            }
        }
        return head;
    }
}