我正在做平衡括号问题(https://www.hackerrank.com/challenges/balanced-brackets),我无法弄清楚我哪里出错了.
例如
3 {[()]} {[(])} {{[[(())]]}}
- >
YES NO YES
我认为这将是一个直截了当的事实,该字符串包含平衡括号,当且仅当对于每一s[i],s[n-i-1]
对它是真的s[i]
是一个右向括号并且s[n-i-1]
是相应的左向括号.
因此我的解决方案
static readonly Dictionarybrackets = new Dictionary () { { '{', '}' }, { '[', ']' }, { '(', ')' } }; static bool IsBalanced(string str) { for(int i = 0, j = str.Length - 1; i < j; ++i, --j) if(!brackets.ContainsKey(str[i]) || brackets[str[i]] != str[j]) return false; return true; }
由于某种原因失败了.
典型的实现基于堆栈:
推动任何开口 [
,{
,(
支架固定到堆
在闭幕 ]
,}
,)
支架,试图弹出顶部的项目,并检查它是否对应于当前右括号:(
对)
等.返回false
如果堆栈是空的或有没有对应.
最后,在处理完最后一个字符后,堆栈应该为空.
执行:
private static DictionaryopenByClose = new Dictionary () { { '}', '{' }, { ']', '[' }, { ')', '(' }, }; private static bool IsBalanced(string source) { if (string.IsNullOrEmpty(source)) return true; Stack brackets = new Stack (); foreach (char ch in source) { char open; if (openByClose.Values.Contains(ch)) // ch is an opening bracket brackets.Push(ch); else if (openByClose.TryGetValue(ch, out open)) // ch is a closing bracket if (!brackets.Any()) return false; // too many closing brackets, e.g. "())" else if (brackets.Pop() != open) return false; // brackets don't correspond, e.g. "(]" } return !brackets.Any(); // too many opening brackets, e.g. "(()" }