[LeetCode] 678. Valid Parenthesis String

dinfer 發布于2019-08-16 13:42 / 2363人閱讀

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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