Java solution using LinkedList


  • 1
    H

    Input 0,1,2 (respectively stands for '(', ')', "()" ) to a linked list, then find the longest subsequence of 2.

    public int longestValidParentheses(String s) {
        int n = s.length();
        if(s.length() < 2) return 0;
        LinkedList<Integer> list = new LinkedList<>();
        int left = 0;
        for(char c : s.toCharArray())
        {
        	if(c == '(')
        	{
        		list.add(0);
        		left++;
        	}
        	else
        	{
        		if(left > 0)
        		{
        			list.removeLastOccurrence(0);
        			list.add(2);
        			left--;
        		}
        		else
        		{
        			list.add(1);
        		}
        	}
        }
        int two = 0;
        int max = 0;
        boolean flag = true;
        for(int num : list)
        {
        	if(num == 2)
        	{
        	two++;
        	if(!flag) flag = true;
        	}
        	else
        	{
        	    if(flag)
        	    {
        		max = Math.max(two, max);
        		two = 0;
        		flag = false;
        	    }
        	}
        }
        max = Math.max(two, max);
        return 2 * max;
    }

  • 0
    N

    In the second part, I tried:

    int maxCount = 0;
    int two = 0;
    for(int i=0; i<countMap.size(); i++) {
    if(countMap.get(i)==2)
    {
    while(i<countMap.size() && countMap.get(i)==2) {
    two++;
    i++;
    }
    maxCount = Math.max(maxCount, two*2);
    two = 0;
    }
    }
    return maxCount;

    It still seems to me that the run time is O(n) but, mine is much slower than yours. Do you have any idea why?
    mine = 150 ms, yours = 6 ms. Thanks a lot.


  • 0
    N

    I guess I found the solution. for(int num : list) is much faster than for(int i=0; i<countMap.size(); i++).


  • 0
    H

    You're right. Visiting elements of a LinkedList by index is very time-consuming.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.