笔试面试算法经典--最长括号匹配

在求最长括号匹配之前先看看括号下面这个问题：

括号匹配

“ {（）}”这种是括号匹配，而 “{ ] ] { ” 这种就不是括号匹配。判断一个给定的括号字符串是否是匹配的。对于括号匹配这类的问题可以使用 Stack来处理：1 . 当碰到”( [ { “这些左括号就进栈。2 . 如果碰到“) ] }”这些右括号时，如果栈为空，则肯定不匹配，返回false。如果栈不为空，则出栈比较两个括号是否匹配不匹配返回 false 。3 . 如果遍历完整个括号串后栈为空返回true，否则返回false。

例：” ( { } ) [ ] “的匹配过程如下：

①颜色相同的表示同一类型的左右括号。

②碰到两个左括号将它们入栈。

③碰到右括号时出栈比较，如果相同出栈，不同直接返回false。

④匹配完后栈为 null 返回 true，否则返回 false。

public boolean isMatch(String str)
	{
		if(str==null||str.length()==0)
			return false;
			//如果给出的字符串是null 或者长度为0返回false。
		char chs[]=str.toCharArray();
		Stack<Character> stack=new Stack<Character>();
		int i=0;
		String left="([{";
	//用left保存左括号的类型，便于比较。	
		String right=")]}";
	//用right 保存右括号的类型，便于比较。	
		while(i<chs.length)
		{
			if(left.contains(chs[i]+""))
			{
				//如果是左括号，加入栈中
				stack.push(chs[i]);
			}
			else {
				//如果是右括号，如果栈为null 返回false，否则比较栈顶元素与当前元素是否匹配。
				if(stack.isEmpty())
				{
					return false;
				}
				else {
					char topchar=stack.pop();					
					if(left.indexOf(topchar)!=right.indexOf(chs[i]))
					//如果左右括号不匹配返回false。	
					return false;
				}
			}
			i++;
		}		
		return stack.isEmpty();
		//如果栈为空，则返回 true，否则返回 false。
	}

最长括号匹配

求一个括号串的最长括号子串的长度，如 “ ) ( ( ) ( ) ”的最长子串为“ ( ) ( ) ”长度为4。

方法1（暴力法 时间复杂度O（n^2）,空间复杂度O（n））

用二重循环遍历每一个子串，子串是括号匹配的获得子串的长度，使用一个max_len 保存最大括号匹配子串的长度。优点：当左右括号的类型不唯一时也可以判断，缺点：时间复杂度大。

---

代码

public static int longestMatch(String str)
	{		
		if(str==null||str.length()==0)
			return 0;
		int max_len=0;		
		for(int i=0;i<str.length()-1;i++)
		{
			for(int j=i+1;j<str.length();j++)
			{
				String subString=str.substring(i, j+1);
				//遍历每一个子串，如果子串是括号匹配的，更新最大值。
				//BracketsMatch.isMatch(subString)就是上面括号匹配方法。
				if(BracketsMatch.isMatch(subString))
				{
					max_len=Math.max(max_len, j-i+1);
				}
								
			}
			
		}
	
		return max_len;
	}

方法2（ 时间复杂度O（n）,空间复杂度O（n））

利用栈来保存括号的下标信息，并用变量 last 来保存不是匹配括号的最后一个下标，开始时 last=-1，如
）（）（）），开始时 last=-1 ，当碰到左括号时，入栈，碰到右括号时如果栈为空则 last=当前有括号的下标，否则出栈，如果出栈后栈为空，则长度为 当前下标- last 。否则为当前下标- 栈的下一个元素。

---

public static int longestMatch(String str)
	{
		if(str==null||str.length()==0)
			return 0;
		char chs[]=str.toCharArray();
		Stack<Integer> stack=new Stack<Integer>();
		//注意这种方法只能判断一种类型的左右括号，不能同时判断两种及以上的左右括号。
		int i=0,last=-1,max_len=0;
		while(i<chs.length)
		{
			if(chs[i]=='(')
			{
				stack.push(i);
			}
			else {
				if(stack.isEmpty())
				{
					last=i;
				}
				else {
					stack.pop();
					if(stack.isEmpty())
					max_len=Math.max(max_len, i-last);
					else {
						max_len=Math.max(max_len, i-stack.peek());
					}
				}
			}
			i++;						
		}
		return max_len;
	}