括号问题

谁践踏了优雅 2023-02-25 08:57 4阅读 0赞

# 括号问题 #

刷Leetcode时，遇到过许多括号问题，总结一下

## 有效括号 ##

给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。  
注意空字符串可被认为是有效字符串。

**示例 1:**

输入: "()"
    输出: true

**示例 2:**

输入: "()[]{}"
    输出: true

**示例 3:**

输入: "(]"
    输出: false

**示例 4:**

输入: "([)]"
    输出: false

**示例 5:**

输入: "{[]}"
    输出: true

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/valid-parentheses  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 代码 ###

class Solution {
        
        private HashMap<Character, Character> mappings;
        public boolean isValid(String s) {
        
            if(s==null||s.length()==0) return true;
            this.mappings = new HashMap<Character, Character>();
            this.mappings.put(')', '(');
            this.mappings.put('}', '{');
            this.mappings.put(']', '[');
            Stack<Character> charStack = new Stack<>();
           
            for (int i = 0; i < s.length(); i++) {
        
                char ch = s.charAt(i);
    
                if (this.mappings.containsKey(ch)) {
        
                    char topElement = charStack.empty() ? '#' : charStack.pop();
                    if (topElement != this.mappings.get(ch)) {
        
                        return false;
                    }
    
                }else{
        
                    charStack.push(ch);                
                }
            }
            return charStack.isEmpty();
        }
    }

## 括号生成 ##

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

**示例：**

输入：n = 3
    输出：[
           "((()))",
           "(()())",
           "(())()",
           "()(())",
           "()()()"
         ]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/generate-parentheses  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 代码 ###

class Solution {
        
        List<String> res = null;
        public List<String> generateParenthesis(int n) {
        
              res = new ArrayList<>();
            char [] Parenthesis = new char[2*n];
            for (int i = 0; i < Parenthesis.length; i++) {
        
                Parenthesis[i]='(';
            }
            dfs(Parenthesis,1,0);
            return res;
        }
    
         void dfs(char[] Parenthesis,int index,int count){
        
            if (count==Parenthesis.length/2) {
        
                res.add(String.valueOf(Parenthesis));
                return;
            }
    
            for (int i = index; i < Parenthesis.length; i++) {
        
                if (i+1<(count+1)*2) continue;
                Parenthesis[i] = ')';
                dfs(Parenthesis,i+1,count+1);
                Parenthesis[i]='(';
            }
        }
    }

## 最长有效括号 ##

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

**示例 1:**

输入: "(()"
    输出: 2
    解释: 最长有效括号子串为 "()"

**示例 2:**

输入: ")()())"
    输出: 4
    解释: 最长有效括号子串为 "()()"

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-valid-parentheses  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
     * 困难级别，以后需要回看一下
     */
    public class longestValidParentheses {
        
        //动态规划
        public int LongestValidParentheses(String s) {
        
            int maxans = 0;
            int []dp = new int[s.length()];
            for (int i = 1; i < dp.length; i++) {
        
                if (s.charAt(i)==')') {
        
    
                    if (s.charAt(i-1)=='(') {
        
                        //刚好凑一对
                        dp[i]=(i>2 ? dp[i-2] : 0)+2;
                    }else if(i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '('){
        
                        //跟远方的凑成一对
                        dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                    }
                    maxans = Math.max(maxans, dp[i]);
                }
            }
            return maxans;
        }
    
        //使用栈的方法进行
        public int LongestValidParentheses2(String s) {
        
            int maxans = 0;
            //将下标存进去
            Stack<Integer> stack = new Stack<>();
            stack.push(-1);
            for (int i = 0; i < s.length(); i++) {
        
                if (s.charAt(i) == '(') {
        
                    stack.push(i);
                } else {
        
                    stack.pop();
                    if (stack.empty()) {
        
                        stack.push(i);
                    } else {
        
                        maxans = Math.max(maxans, i - stack.peek());
                    }
                }
            }
            return maxans;
        }
    
        //贪心算法
        public int longestValidParentheses3(String s) {
        
            int left = 0, right = 0, maxlength = 0;
            for (int i = 0; i < s.length(); i++) {
        
                if (s.charAt(i) == '(') {
        
                    left++;
                } else {
        
                    right++;
                }
                if (left == right) {
        
                    maxlength = Math.max(maxlength, 2 * right);
                } else if (right > left) {
        
                    left = right = 0;
                }
            }
            left = right = 0;
            for (int i = s.length() - 1; i >= 0; i--) {
        
                if (s.charAt(i) == '(') {
        
                    left++;
                } else {
        
                    right++;
                }
                if (left == right) {
        
                    maxlength = Math.max(maxlength, 2 * left);
                } else if (left > right) {
        
                    left = right = 0;
                }
            }
            return maxlength;
        }
    
        public static void main(String[] args) {
        
            longestValidParentheses l = new longestValidParentheses();
            String s = "()(())";
            System.out.println(l.LongestValidParentheses(s));
        }
    }