An easy understanding way to solve it


  • 8
    Z

    but maybe with more timewaste.haha

    class LVP{
    
    	public:
    	int lvp( string s ){
    		int len = s.size();
    		if( !len )			// if string is empty, return 0 instantly.
    			return 0;
    		for( int i = 0;i < len;i++ )	
    			if( s[i] == ')' )	
    				for( int j = i - 1;j >= 0;j-- )		// for every ')’,find the first match '(' before it
    					if( s[j] == '(' )	{			// and mark the two with a special flag,like '0'
    						s[i] = '0';
    						s[j] = '0';
    						break;
    					}
    		int max = 0,temp = 0;						
    		for( int i = 0;i < len;i++ )	{			// the problem changed to find the longest '0' in the string
    			if( s[i] == '0' )
    				temp++;
    			else	{
    				max = temp > max ? temp : max;
    				temp = 0;
    			}
    		}
    		max = temp > max ? temp : max;				// longest '0'sequence may still stored in temp
    		return max;
    	}
    };

  • 0
    S

    Hi @zergzz, thanks for your posting, pay attention to translate all Chinese to English next time, and the code format as well.


  • 0
    C

    Thank you for your answer it really helped me a lot :) Just a quick advice, we could avoid the inside loop of finding the first match '(' for every ')' if we use a stack to keep the index of every '('


  • 0
    D

    Your advice is quite clever, and the time-complexity will be reduced from N^2 to N.


Log in to reply
 

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