如何檢查字符串是否包含Java中的關閉組括號

如何檢查字符串以進行正確分組。例如，下面的組正確完成：如何檢查字符串是否包含Java中的關閉組括號

({}) 
[[]()] 
[{()}]

下被錯誤地進行：

{(}) 
([] 
[])

正確的字符串不能以錯誤的順序緊密羣體中，打開一個組，但未能將其關閉，或者在打開之前關閉一個組。

可能包含任何符號「（）」「{}」或「[]」以創建組的輸入字符串。如果字符串爲空或以其他方式正確分組，則輸出返回True;如果分組不正確，則返回False。

任何人都可以給我一些提示。

來源

2015-10-19 Khuong

嘗試使用堆棧 – naresh

在Java中使用堆棧（deque）。 –

可能的重複[檢查給定的字符串是否平衡括號字符串，遞歸]（http://stackoverflow.com/questions/20506179/check-if-a-given-string-is-balanced-brackets-string-recursively） –

主要想法是使用Stack來跟蹤預期的下一個對應支架。下面的代碼將工作：

public boolean isValid(String s) { 
    HashMap<Character, Character> closeBracketMap = new HashMap<Character, Character>(); 
    closeBracketMap.put(')', '('); 
    closeBracketMap.put(']', '['); 
    closeBracketMap.put('}', '{'); 
    HashSet<Character> openBracketSet = new HashSet<Character>(
     closeBracketMap.values()); 
    Stack<Character> stack = new Stack<Character>(); 

    char[] chars = s.toCharArray(); 
    for (int i = 0; i < chars.length; i++) { 
     char cur = chars[i]; 
     if (openBracketSet.contains(cur)) { 
      stack.push(cur); 
     } else { // close brackets 
      if (stack.isEmpty()) { 
       return false; 
      } 
      if (closeBracketMap.get(cur) != stack.peek()) { 
       return false; 
      } 
      stack.pop(); 
     } 
    } 

    return stack.isEmpty(); 
}

來源

2015-10-19 04:00:37

看起來非常複雜：0 –

@KickButtowski對於'O（n）'的最佳運行時間來說這不是太複雜:) –

@ khuong291我已經提出了你的問題。 –

我真的不希望使用堆棧，周圍試圖東西之後。這是我的解決方案。我認爲這是非常明確和簡單的：

public class Groups{ 
    public static boolean groupCheck(String s) { 
    int len; 
    do { 
     len = s.length(); 
     s = s.replace("()", ""); 
     s = s.replace("{}", ""); 
     s = s.replace("[]", ""); 
    } while (len != s.length()); 
    return s.length() == 0; 
    } 
}

這意味着我們將刪除一個一個括號。它將刪除「[]」，「[]」，「（）」。然後s =「（{}）」（s.length（）= 4）它將繼續刪除「{}」。那麼s =「（）」（s.length（）= 2），它將繼續刪除「（）」。那麼s =「」（s.length（）= 0）。它會打破循環，因爲（（len == 10）！=（s.length（）== 0））。然後我們將能夠檢查它是否屬實。 :)

來源

2015-10-19 04:15:17 Khuong

解決方案的最壞情況運行時間是'O（n^2）'，n是字符串的長度，因爲每個replace（）成本都是O（n） –

如何檢查字符串是否包含Java中的關閉組括號

回答

相關問題