[LeetCode] 678. Valid Parenthesis String

dinfer 发布于2019-08-16 13:42 / 2364人阅读

Problem

Given a string containing only three types of characters: "(", ")" and "*", write a function to check whether this string is valid. We define the validity of a string by these rules:

Any left parenthesis "(" must have a corresponding right parenthesis ")".
Any right parenthesis ")" must have a corresponding left parenthesis "(".
Left parenthesis "(" must go before the corresponding right parenthesis ")".
"*" could be treated as a single right parenthesis ")" or a single left parenthesis "(" or an empty string.
An empty string is also valid.
Example 1:
Input: "()"
Output: True
Example 2:
Input: "(*)"
Output: True
Example 3:
Input: "(*))"
Output: True
Note:
The string size will be in the range [1, 100].

Solution

class Solution {
    public boolean checkValidString(String s) {
        return helper(s, 0, 0);
    }
    private boolean helper(String s, int index, int count) {
        if (index == s.length()) {
            return count == 0;
        }
        
        if (count < 0) return false;
        char ch = s.charAt(index);
        if (ch == "(") return helper(s, index+1, count+1);
        else if (ch == ")") return helper(s, index+1, count-1);
        else return helper(s, index+1, count-1) || helper(s, index+1, count+1) || helper(s, index+1, count);
    }
}

GPU云服务器云服务器 LeetCode_String Parenthesis 网络连接错误678 LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72188.html

LeetCode 606. Construct String from Binary Tree 二叉

摘要：题意从一颗二叉树转为带括号的字符串。这题是的姊妹题型，该题目的解法在这里解法。 LeetCode 606. Construct String from Binary Tree You need to construct a string consists of parenthesis and integers from a binary tree with the preorder t...

mikyou 2019-08-16 13:31 评论0 收藏0
[LeetCode] 606. Construct String from Binary Tree

Problem You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way. The null node needs to be represented by empty parenthesis pair (). And...

madthumb 2019-08-16 13:39 评论0 收藏0
LeetCode 536. Construct Binary Tree from String 从带

摘要：题意从一个带括号的字符串，构建一颗二叉树。其中当而时，展示为一个空的括号。同时要考虑负数的情况，所以在取数字的时候，必须注意所在位置。遇到则从栈中出元素。最后中的元素就是，返回栈顶元素即可。 LeetCode 536. Construct Binary Tree from String You need to construct a binary tree from a string ...

tabalt 2019-08-16 13:31 评论0 收藏0
301. Remove Invalid Parenthesis

摘要：问题解答这题是看里面的的代码如果比大或等的话，就继续扫下去否则，我们就找到当前有可能删去的，然后删掉看新的如果只从左到右扫了，还是的时候，我们还要再从右往左扫一遍否则两遍都扫完了，就加入结果中去问题：Remove the minimum number of invalid parentheses in order to make the input string valid. Ret...

lentoo 2019-08-14 14:17 评论0 收藏0
439. Ternary Expression Parser

摘要：所组成的最小单位，可以看作一对括号。从左往右看，作为决定一组完整最小单位的符号。每次找到一对就可以按分为左右两个子问题递归解决。从右往左看，作为决定最小单位的符号，每次遇到一个，就拆解离最近的两个小单位。宏观上看是，从小到大。 Given a string representing arbitrarily nested ternary expressions, calculate th...

zhunjiee 2019-08-14 18:00 评论0 收藏0