频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
String-678-Valid Parenthesis String
2018-02-12 14:59:08         来源:MayUWell  
收藏   我要投稿

Description:
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:

/*
*贪心算法。lo表示可能的最少的'('数,hi表示可能的最多的'('数。符合的条件为lo<=0并且hi>=0.
*因此每轮迭代lo取Math.max(lo,0),并且当hi<0(表示左括号最多也不会多于0个)可以直接退出循环。
*退出循环后判断lo是否等于0即可
*/
class Solution {
    public boolean checkValidString(String s) {
       int lo = 0, hi = 0;
       for (char c: s.toCharArray()) {
           lo += c == '(' ? 1 : -1;
           hi += c != ')' ? 1 : -1;
           if (hi < 0) break;
           lo = Math.max(lo, 0);
       }
       return lo == 0;
    }
}
点击复制链接 与好友分享!回本站首页
上一篇:codeforces917b(dp) 编程题
下一篇:Basic Calculator
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站