local 1 ms, after submit time exceeded.


  • 0
    J
    public class Solution
        {
            char[] sourceArray = null;
    
            public int LongestValidParentheses(string s)
            {
                sourceArray = s.ToCharArray();
    
                Hashtable htCouples = new Hashtable();
    
                GetAll(sourceArray, htCouples);
    
                if (htCouples.Count > 0)
                {
                    int result = 0;
                    foreach (DictionaryEntry de in htCouples) //ht为一个Hashtable实例
                    {
                        int total = (int)(de.Value) - (int)de.Key;
                        if (total > result)
                        {
                            result = total;
                        }
                    }
    
                    return result + 1;
                }
                
                return 0;
            }
    
            private void GetAll(char[] array, Hashtable ht)
            {
                int beginPosition = -1;
                int endPosition = -1;
                FindFirstCouple(array, ref beginPosition, ref endPosition);
    
                if (beginPosition != -1) // found
                {
                    array[beginPosition] = '\0';
                    array[endPosition] = '\0';
    
                    // to find joinable record in hashtable
                    if (beginPosition > 0 && array[beginPosition - 1] == '\0')
                    {
                        int key = FindKey(beginPosition - 1, ht);
                        ht[key] = endPosition;
                    }
                    else if (beginPosition < array.Length - 2 && array[beginPosition + 1] == '\0' && beginPosition + 1 != endPosition)
                    {
                        ht.Remove(beginPosition + 1);
                        ht.Add(beginPosition, endPosition);
                    }
                    else
                    {
                        ht.Add(beginPosition, endPosition);
                    }
    
                    GetAll(array, ht);
                }
            }
    
            private int FindKey(int value, Hashtable ht)
            {
                foreach (DictionaryEntry de in ht)
                {
                    if ((int)de.Value == value)
                    {
                        return (int)de.Key;
                    }
                }
    
                return -1;
            }
    
            private void FindFirstCouple(char[] array, ref int begin, ref int end)
            {
                for (int i = 0; i < array.Length - 1; i++)
                {
                    if (array[i] == '(')
                    {
                        for (int j = i + 1; j < array.Length; j++)
                        {
                            if (array[j] == '(')
                            {
                                break;
                            }
    
                            if (array[j] == ')')
                            {
                                begin = i;
                                end = j;
                                return;
                            }
                        }
                    }
                }
            }
        }
    

Log in to reply
 

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