LeetCode #4

What I’ve Learned

First, Sorting alphabetical and comparing between first and last value for continuous characters is astonishing idea.
Second, Stack I can use stack to check if it matched or not.
Third, HashMap for mapping two different values.
Fourth, ListNode has a similar patterns. It uses while and pointer. Fifth, double pointers can be used anywhere.

Disclaimer

My LeetCode is free plan. I am posting just the free algorithms for now on. Also, I am using JAVA to code.

14. Longest Common Prefix

My Solution

I came up with comparing the first String with others and put it inside a list, combine at final step. It passed the given test but, when submitting it didn’t worked. Problem was that it needs to be continuous. I didn’t know how to do it so, I saw the solution.

class Solution {
    public String longestCommonPrefix(String[] strs) {
    	String reference = strs[0];
    	ArrayList<Character> list = new ArrayList<>();
    	boolean add = true;

    	for(int i = 0; i<reference.length(); i++) {
    		for(int j =1; j<strs.length; j++) {
    			if(strs[j].indexOf(reference.charAt(i)) == -1) {
    				add = false;
    				break;
    			}
    				
    			else
    				add = true;
    		}
    		if(add)
    			list.add(reference.charAt(i));
    	}
    	
    	 StringBuilder sb = new StringBuilder();
         for (char c : list) {
             sb.append(c);
         }
    	
    	return sb.toString(); 
    }
}

Solution

This question is tough. Sorting the array and comparing first and last value. Sorting alphabetical. How can I come up with that idea? Sorting and comparing the first and last is something.

class Solution {
    public String longestCommonPrefix(String[] strs) {
        Arrays.sort(strs);
        String s1 = strs[0];
        String s2 = strs[strs.length-1];
        int idx = 0;
        while(idx < s1.length() && idx < s2.length()){
            if(s1.charAt(idx) == s2.charAt(idx)){
                idx++;
            } else {
                break;
            }
        }
        return s1.substring(0, idx);
    }
}

20. Valid Parentheses

My Solution

At a first glance, I thought it was easy. But, it took few hours to make a wrong answer. It is a tough question if you don’t know about stack. I didn’t know it too. So, I saw the Solution.

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> mapping = new HashMap<>();
        mapping.put(')', '(');
        mapping.put('}', '{');
        mapping.put(']', '[');

        for (char c : s.toCharArray()) {
            if (mapping.containsValue(c)) {
                stack.push(c);
            } else if (mapping.containsKey(c)) {
                if (stack.isEmpty() || mapping.get(c) != stack.pop()) {
                    return false;
                }
            }
        }

        return stack.isEmpty();        
    }
}

I didn’t come up with stack. It could be more easier if I used stack. And mapping with hashmap is a great idea. I need to review this question again.

21. Merge Two Sorted Lists

My Solution

This question is tough. The most confusing part was that returning form seems like an array but actual return type is ListNode. I saw the solution to make my own and wasn’t really successful.

class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) {
    	 this.val = val; 
    	 }
     ListNode(int val, ListNode next) {
    	 this.val = val; this.next = next; 
    	 }
 }

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    	ListNode pointer = new ListNode();
    	ArrayList<ListNode> result_arr = new ArrayList<>();
    	
    	while(list1 != null || list2 != null) {
    		if(list1.val >= list2.val) {
    			result_arr.add(list1);
    			list1 = list1.next;
    		}else {
    			result_arr.add(list2);
    			list2 = list2.next;
    		}
    	}
    	pointer = result_arr.getFirst();    	
    	return pointer.next;
    }
}

Solution

Using dummy pointer. I was thinking of it but, I didn’t know how to use it. It seems most of the ListNode question looks alike. Using while(list1 != null){} statement and using dummy parameter. Also, it’s using reference modification. This is tough.

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                cur.next = list2;
                list2 = list2.next;
            } else {
                cur.next = list1;
                list1 = list1.next;
            }
            cur = cur.next;
        }

        cur.next = (list1 != null) ? list1 : list2;

        return dummy.next;        
    }
}

26. Remove Duplicates from Sorted Array

My Solution

I tried to solve with linked list or array list but, it was impossible. After 30 minutes, I came up with stack solution. First, add first value of nums in stack. Then continue if it eqauls the value inside stack or push if it isn’t already in stack. I thought it was pretty good solution, but there are better ways.

class Solution {
    public int removeDuplicates(int[] nums) {
    	Stack<Integer> stack = new Stack<>();
    	stack.push(nums[0]);
    	
    	for(int i =1; i<nums.length; i++) {
    		if(stack.contains(nums[i])) 
    			continue;
    		else
    			stack.push(nums[i]);
    	}
        
    	for(int j =0; j<stack.size(); j++) {
    		nums[j] = stack.get(j);
    	}
    	return stack.size();
    }
}

Solution

This is quite simple approach. Using two pointers to check. I still think that I cannot come up with this idea. It’s moving one by one through comparing values next to each other.

class Solution {
    public int removeDuplicates(int[] nums) {
        int j = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[j] = nums[i];
                j++;
            }
        }
        return j;
    }
}