One Java solution based on FIFO


  • 0
    K

    public List<String> generateParenthesis(int n) {
    LinkedList<String> result = new LinkedList<>();
    for (int i = 0; i < n2; i++) {
    if (i == 0) {
    result.add("(");
    } else {
    while (result.peek().length() == i) {
    String oldStr = result.removeFirst();
    //追加逻辑 当左括号个数达到上限时,添加右括号,否则当oldStr为完整的括号组合时,只能添加左括号,否则左右括号均可
    if (getLeftCharLen(oldStr) >= n) {
    String newStr = oldStr+")";
    result.add(newStr);
    }else{
    String newStrLeft = oldStr+"(";
    result.add(newStrLeft);
    if(!isValid(oldStr)){
    String newStrRight = oldStr+")";
    result.add(newStrRight);
    }
    }
    }
    }
    }
    return result;
    }
    /
    *
    * 判断字符是否是合法的括号对
    *
    * @param s
    * @return
    */
    public boolean isValid(String s) {
    Map<Character, Integer> LeftMap = new HashMap<>();
    Map<Character, Integer> RightMap = new HashMap<>();
    LeftMap.put('(', 1);
    RightMap.put(')', 1);
    Stack<Character> stack = new Stack<>();
    char[] chars = s.toCharArray();
    stack.push(chars[0]);
    for (int i = 1; i < chars.length; i++) {
    Character newChar = chars[i];//当前的字符
    Character peek = null;//栈顶字符
    if (!stack.isEmpty()) {
    peek = stack.peek();
    }
    if (peek != null) {
    //栈顶元素尝试从左括号里面找
    Integer peekIndex = LeftMap.get(peek);
    //新来的元素尝试从右括号里面找
    Integer newIndex = RightMap.get(newChar);
    if ((peekIndex != null) && (newIndex != null) && peekIndex == newIndex) {
    stack.pop();
    continue;
    }
    }
    stack.push(newChar);
    }
    return stack.isEmpty();
    }
    private int getLeftCharLen(String s) {
    int result = 0;
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
    if (chars[i] == '(') {
    result++;
    }
    }
    return result;
    }


Log in to reply
 

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