[LeetCode] 20. Valid Parentheses

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.

Subscribe to see which companies asked this question

public class Solution {
    public boolean isValid(String s) {
        
        int len = s.length();
        
        if(0 == len)
            return true;
        
        // can not use char in template
        // Use queue instead of stack at first ........, can't find the bug even.
        Stack pq = new Stack();

        /*
        pq.peek() == new Character('[') 
        OK.
        pq.peek() == '['
        '[' == pq.peek()
        null return can not compare with primitive char
        null pointer execption
        */
        

        for(int i = 0; i < len; ++i){
            
            char c = s.charAt(i);
            
            if(c =='(' || c =='{' || c =='['){
                pq.push(c);
            // The peek operation is different from queue to stack. We can peek empty queue, but not for stack. 
            }else if(pq.empty()){
                return false;
            }else{
                if(c == ')')
                    // use poll instead of peek here first, not working for input "]", empty queue, must peek before poll
                    if(pq.peek().charValue() == '(') pq.pop(); else return false;
                if(c == '}')
                    if(pq.peek().charValue() == '{') pq.pop(); else return false;
                if(c == ']')
                    if(pq.peek().charValue() == '[') pq.pop(); else return false;
            }
        }
        
        // shouldn't return true here. pq must be empty
        return pq.empty();
        
    }
}

[Leetcode] 19. Remove Nth Node From End of List

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.
Try to do this in one pass.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(null == head)
            return null;
        
        int k = n;
        
        ListNode preHead = new ListNode(0);
        
        preHead.next = head;
        
        ListNode i = preHead;
        ListNode j = head;
        
        while(null != j.next){
            j = j.next;
            if(k > 1){
                --k;
            }else{
                i = i.next;
            }
        }
        
        i.next = i.next.next;
        
        return preHead.next;
    }
}

[LeetCode] 18. 4Sum

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)

1. Call 3 sum.

public class Solution {
    
    public List> threeSum(int[] nums, int startI, int target) {
        int len = nums.length;
        List> ret = new ArrayList>();
        for(int i = startI; i < len; ++i){
            if(i > startI && nums[i-1] == nums[i])
                continue;
            int x = i+1;
            int y = len-1;
            while(x < y){
                int sum = nums[x] + nums[y] + nums[i];
                if(target == sum){
                    Integer[] res = {nums[x], nums[y], nums[i]};
                    ret.add(Arrays.asList(res));
                    --y;
                    while(y >= startI && nums[y+1] == nums[y]){
                        --y;
                    }
                    ++x;
                    while(x < len && nums[x-1] == nums[x]){
                        ++x;
                    }
                }else if(target < sum){
                    --y;
                    while(y >= startI && nums[y+1] == nums[y]){
                        --y;
                    }
                }else{
                    ++x;
                    while(x < len && nums[x-1] == nums[x]){
                        ++x;
                    }
                }
            }
        }
        
        return ret;
    }
    
    public List> fourSum(int[] nums, int target) {
        int len = nums.length;
        List> ret = new ArrayList>();
        Arrays.sort(nums);
        
        for( int i = 0; i < len -3; ++i){
            if(i > 0 && nums[i-1] == nums[i])
                continue;
            int j = i+1;
            int threeSumTarget = target - nums[i];
            List> resThree = threeSum(nums, j, threeSumTarget);
            
            for(List l : resThree){
                ArrayList t = new ArrayList(l);
                t.add(nums[i]);
                Collections.sort(t);
                ret.add(t);
            }
        }
        
        return ret;
    }
}

2. Build K Sum

public class Solution {
    
    public List> kSum(int[] nums, int startI, int target, int k) {
        
        int len = nums.length;
        
        List> ret = new ArrayList>();
        
        //        List> ret = null can not pass input [0] in 4 sum. All loop return immedicately, including twoSum. It can be controlled by if(4 > len) in main function.
        
        if(2 == k){
            
            // error : forgot to initialize the ret, List> ret = new ... was removed because line 44, ret = kSum(nums, i+1, target - nums[i], k-1);

            ret = new ArrayList>();
            
            int i = startI;
            int j = len -1;
            
            while(i < j){

                int sum = nums[i] + nums[j];
                if(sum == target){
                    List twoSumItem = new ArrayList();
                    twoSumItem.add(nums[i]);
                    twoSumItem.add(nums[j]);
                    ret.add(twoSumItem);
                    
                    // Here, forgot to increase and decrease index, time limit exceeded. Brain power depleted after 2 hour coding.
                    ++i;
                    while(i < len && nums[i-1] == nums[i]){
                        ++i;
                    }
                    --j;
                    while(j >= startI && nums[j+1] == nums[j]){
                        --j;
                    }
                // get the wrong sign, increasing decreasing index with wrong direction, get no answer or little answer.    
                }else if(sum < target){
                    ++i;
                    while(i < len && nums[i-1] == nums[i]){
                        ++i;
                    }
                }else{
                    --j;
                    while(j >= startI && nums[j+1] == nums[j]){
                        --j;
                    }
                }
            }
            
            return ret;
        }
        
        for(int i = startI; i < len; ++i){
            if(i > startI && nums[i-1] == nums[i])
                continue;
            
            // Tried to optmize code
            // Assigned ret as the return from k-1 sums, while forgot k-1 sums were called multiple times, previuos ret were washed out.
            /*
            ret = kSum(nums, i+1, target - nums[i], k-1);
            
            for(List l : ret){
                l.add(nums[i]);
            }
            */
            List> kMOneRes = kSum(nums, i+1, target - nums[i], k-1);
            for(List l : kMOneRes){
                l.add(nums[i]);
            }
            
            ret.addAll(kMOneRes);
            
        }

        return ret;
    }
    
    public List> fourSum(int[] nums, int target) {
        int len = nums.length;
        
        List> ret = new ArrayList>();
        if(4 > len)
            return ret;
        
        Arrays.sort(nums);
        
        ret = kSum(nums, 0, target, 4);
        
        for(List l : ret){
            Collections.sort(l);
        }

        return ret;
    }
}

3. Pariwise, them two sum. Good solution, reduce complexity to O(N^2), but it is not easy to handle replicated answer. Plus, it can be O(n^4) in worst case. Consider 0 0 0 0 0 1 1 1 1 1, target 1. HashMap : 0: (0, 0) ... , 1: (0, 1) ... , 2 : (1, 1) .... For each key, it contains a list with length O(n^2), Then for target 1 = key 0 + key 1, do pair-wise match between two O(n^2) lists. Could we remove duplicates before hand? It does not sounds possible. Another solution could be divide 4 sum into 0 + 4, 1 + 3, 2 + 2, 3 + 1, 4 + 0 then conquer?

3.

3.

[LeetCode] 17. Letter Combinations of a Phone Number

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.

public class Solution {
    
    public void letterCombinationsAux(String digits, int i, char[][] dial, StringBuilder sb, List res){
        
        int len = digits.length();
        
        if(i >= len){
            res.add(sb.toString());
            return;
        }
        
        int number = Character.getNumericValue(digits.charAt(i));
        
        for(char c : dial[number]){
            sb.append(c);
            letterCombinationsAux(digits, i+1, dial, sb, res);
            sb.deleteCharAt(sb.length()-1);
        }
        
        return;
        
    }
    
    public List letterCombinations(String digits) {
        char[][] dial = {{}, {}, {'a','b','c'},{'d','e','f'}, {'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
        
        int len = digits.length();
        ArrayList res = new ArrayList();
        
        if(0 == len)
            return res;
            
        letterCombinationsAux(digits, 0, dial, new StringBuilder(), res);
        
        return res;
    }
}

public class Solution {
    
    public void letterCombinationsAux(String digits, int i, char[][] dial, char[] path, List res){
        
        int len = digits.length();
        
        if(i >= len){
            res.add(new String(path));
            return;
        }
        
        int number = Character.getNumericValue(digits.charAt(i));
        
        for(char c : dial[number]){
            path[i] = c;
            letterCombinationsAux(digits, i+1, dial, path, res);
        }
        
        return;
        
    }
    
    public List letterCombinations(String digits) {
        char[][] dial = {{}, {}, {'a','b','c'},{'d','e','f'}, {'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
        
        int len = digits.length();
        List res = new ArrayList();
        
        if(0 == len)
            return res;
            
        letterCombinationsAux(digits, 0, dial, new char[len], res);
        
        return res;
    }
}

[LeetCode] 16. 3Sum Closest

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).

Subscribe to see which companies asked this question

public class Solution {
    
    int keepDec(int i, int[] nums){
        --i;
        while(i>=0 && nums[i]==nums[i + 1]){
            --i;
        }
        return i;
    }
    int keepInc(int i, int[] nums){
        ++i;
        while(i= 0 && y < len){
                int sum = nums[i] + nums[x] + nums[y];
                
                if(Math.abs(sum - target) < Math.abs(res - target)){
                    res = sum;
                }
            
                if(sum == target){
                    return target;
                }
                else if( sum > target){
                    y = keepDec(y, nums);
                }else{
                    x = keepInc(x, nums);
                }
            }
            
            i = keepInc(i, nums);
        }
        
        return res;
        
    }
}

[LeetCode] 15. 3Sum

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)

public class Solution {
    public List> threeSum(int[] nums) {
        int len = nums.length;
        List> ret = new ArrayList>();
        Arrays.sort(nums);
        for(int i = 0; i < len; ++i){
            if(i > 0 && nums[i-1] == nums[i])
                continue;
            int x = i+1;
            int y = len-1;
            while(x < y){
                int sum = nums[x] + nums[y];
                sum += nums[i];
                if(0 == sum){
                    Integer[] res = {nums[x], nums[y], nums[i]};
                    Arrays.sort(res);
                    ret.add(Arrays.asList(res));
                    --y;
                    while(y >= 0 && nums[y+1] == nums[y]){
                        --y;
                    }
                    ++x;
                    while(x < len && nums[x-1] == nums[x]){
                        ++x;
                    }
                }else if(0 < sum){
                    --y;
                    while(y >= 0 && nums[y+1] == nums[y]){
                        --y;
                    }
                }else{
                    ++x;
                    while(x < len && nums[x-1] == nums[x]){
                        ++x;
                    }
                }
            }
        }
        
        return ret;
    }
}

[LeetCode] 14. Longest Common Prefix My Submissions Question

class Solution {
public:
    string longestCommonPrefix(vector &strs) {
        string comPrefix;
        if(strs.empty()) return comPrefix;

        // It is better to compare with the first element instead of previous element.

        for(int i=0; i=strs[j].size() || strs[j][i]!=strs[0][i])
                    return comPrefix;
            }
            comPrefix.push_back(strs[0][i]);
        }
        return comPrefix;
    }
};