有人能解释一下我的方法有什么问题吗?

wgmfuz8q  于 2021-07-06  发布在  Java
关注(0)|答案(3)|浏览(386)

我试图解决这个问题。https://leetcode.com/problems/valid-parentheses/. 但是,我不知道在第二个for循环中是否可以比较s.charat(i)和stack.pop()。
基本上,我的方法是这样的。将整个字符串放入堆栈,然后使用stack.charat(i)遍历堆栈的前半部分,并使用stack.pop()将其与后半部分进行比较。我只是想知道在我的代码中可能会出什么问题,因为当我期望一个真值时得到了一个假值。我只是想弄明白我的观念是否有缺陷?

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        boolean done = false;

        if(s.length() < 2)
            return true;

        for(int i = 0; i < s.length(); i++){
            stack.push(s.charAt(i));
        }

        for(int i = 0; i < s.length()/2; i++){
            if(s.charAt(i) == stack.pop())
                done = true;
        }

        return done;   
    }
}
qzlgjiam

qzlgjiam1#

而您的代码可能适用于字符串,例如“ {([])} “和” (()) ,你假设弦是对称的。一个有效的输入,例如“ {()[]} “不会传入您的代码,因为它不是对称的。修改代码以说明不对称性。提示:当字符是结束字符时,可能会弹出2个元素,如“)”“}”和“]”。

lkaoscv7

lkaoscv72#

您的代码首先迭代到字符串的中间并填充堆栈,然后从中间到结尾弹出堆栈。换句话说,您隐式地假设一个有效字符串的前半部分是各种类型的左括号,第二部分是它们相应的右括号(例如。 ([]) 或者 {[()]} ). 然而,这些并不是唯一有效的字符串-没有限制规定右括号不能跟在左括号后面,只要成对匹配-例如。, (()()) 是有效字符串。
与其假设字符串中的位置,不如遍历字符串,对于每个字符,如果是左括号,则将其推到堆栈中,如果是右括号,则弹出堆栈并比较两个字符:

private static final Map<Character, Character> PARENS = new HashMap<>();
static {
    PARENS.put('(', ')');
    PARENS.put('[', ']');
    PARENS.put('{', '}');
}
public static boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();

    for (int i = 0; i < s.length(); ++i) {
        char ch = s.charAt(i);
        if (PARENS.containsKey(ch)) {
            stack.push(ch);
        } else {
            if (stack.isEmpty()) {
                return false;
            }
            char match = stack.pop();
            if (ch != PARENS.get(match)) {
                return false;
            }
        }
    }

    return stack.isEmpty();
}
ncecgwcz

ncecgwcz3#

您应该检查字符串中的括号是否匹配:对于 '(' 有一个匹配的 ')' . 但是,请注意 '(' 不等于字符 ')' .
您的代码正在检查字符串是否匹配一个模式,其中字符串的后半部分与字符串的前半部分相反,如 {[))[{ . 换句话说,您正在检查输入是否是回文。
您应该采取的方法是只在堆栈中存储起始括号:

for(int i = 0; i < s.length(); i++){
        if s.charAt(i) is an open bracket:
            stack.push(s.charAt(i));
        else:
            "pop" a character from stack
            if it's '(' make sure that s.charAt(i) is ')'
            if it's '[' make sure that s.charAt(i) is ']'
            if it's '{' make sure that s.charAt(i) is '}'
    }

相关问题