• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode678.有效的括号字符串|ValidParenthesisString

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10498224.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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:

  1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
  2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
  3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
  4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
  5. An empty string is also valid. 

Example 1:

Input: "()"
Output: True 

Example 2:

Input: "(*)"
Output: True 

Example 3:

Input: "(*))"
Output: True 

Note:

  1. The string size will be in the range [1, 100].

给定一个只包含三种字符的字符串:(  和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则:

  1. 任何左括号 ( 必须有相应的右括号 )
  2. 任何右括号 ) 必须有相应的左括号 ( 。
  3. 左括号 ( 必须在对应的右括号之前 )
  4. * 可以被视为单个右括号 ) ,或单个左括号 ( ,或一个空字符串。
  5. 一个空字符串也被视为有效字符串。

示例 1:

输入: "()"
输出: True

示例 2:

输入: "(*)"
输出: True

示例 3:

输入: "(*))"
输出: True

注意:

  1. 字符串大小将在 [1,100] 范围内。

4ms

 1 class Solution {
 2     func checkValidString(_ s: String) -> Bool {
 3         let left = Character("(")
 4         let right = Character(")")
 5         let anyMatch = Character("*")
 6         var minLeft = 0
 7         var maxLeft = 0
 8         for char in s {
 9             if char == left {
10                 minLeft += 1
11                 maxLeft += 1
12             } else if char == right {
13                 minLeft -= 1
14                 maxLeft -= 1
15             } else if char == anyMatch {
16                 minLeft -= 1
17                 maxLeft += 1
18             }
19             minLeft = max(0, minLeft)
20             if maxLeft < 0 {
21                 return false
22             }
23         }
24         return minLeft == 0
25     }
26 }

8ms

 1 class Solution {
 2     func checkValidString(_ s: String) -> Bool {
 3         let left = Character("(")
 4         let right = Character(")")
 5         let anyMatch = Character("*")
 6         var count = 0
 7         for char in s {
 8             if char == right {
 9                 count -= 1
10             } else {
11                 count += 1
12             }
13             if count < 0 {
14                 return false
15             }
16         }
17         count = 0
18         for char in s.reversed() {
19             if char == left {
20                 count -= 1
21             } else {
22                 count += 1
23             }
24             if count < 0 {
25                 return false
26             }
27         }
28         return true
29     }
30 }

Runtime: 12 ms
Memory Usage: 19.7 MB
 1 class Solution {
 2     func checkValidString(_ s: String) -> Bool {
 3         var arr:[Character] = Array(s)
 4         var left:[Int] = [Int]()
 5         var star:[Int] = [Int]()
 6         for i in 0..<arr.count
 7         {
 8             if arr[i] == "*"
 9             {
10                 star.append(i)
11             }
12             else if arr[i] == "("
13             {
14                 left.append(i)
15             }
16             else
17             {
18                 if left.isEmpty && star.isEmpty 
19                 {
20                     return false
21                 }
22                 if !left.isEmpty 
23                 {
24                     left.removeLast()
25                 }
26                 else 
27                 {
28                     star.removeLast()
29                 }
30             }            
31         }
32         while(!left.isEmpty && !star.isEmpty)
33         {
34             if left.last! > star.last!
35             {
36                 return false
37             }
38             left.removeLast()
39             star.removeLast()
40         }
41         return left.isEmpty
42     }
43 }

16ms

 1 class Solution {
 2     func checkValidString(_ s: String) -> Bool {
 3         let left = Character("(")
 4         let right = Character(")")
 5         let anyMatch = Character("*")
 6         var leftStack = [Int]()
 7         var anyMatchStack = [Int]()
 8         for (i, char) in s.enumerated() {
 9             if char == right {
10                 if let top = leftStack.last {
11                     leftStack.popLast()
12                 } else if let top = anyMatchStack.last {
13                     anyMatchStack.popLast()
14                 } else {
15                     return false
16                 }
17             } else if char == left {
18                 leftStack.append(i)
19             } else if char == anyMatch {
20                 anyMatchStack.append(i)
21             }
22         }
23         var leftIndex = leftStack.count - 1
24         var anyMatchIndex = anyMatchStack.count - 1
25         while leftIndex >= 0 && anyMatchIndex >= 0 {
26             if leftStack[leftIndex] > anyMatchStack[anyMatchIndex] {
27                 return false
28             }
29             leftIndex -= 1
30             anyMatchIndex -= 1
31         }
32         return leftIndex < 0
33     }
34 }

260ms

 1 class Solution {
 2     func checkValidString(_ s: String) -> Bool {
 3          let str = Array(s)
 4         var memo = [[Int]].init(repeating: [Int].init(repeating: -1, count: s.count), count: s.count)
 5         
 6         func isValid(_ l: Int, _ r: Int) -> Int {
 7             guard l <= r else {
 8                 return 1
 9             }
10             guard memo[l][r] == -1 else {
11                 return memo[l][r]
12             }
13             if l == r && str[l] == "*" {
14                 memo[l][r] = 1
15                 return 1
16             }
17             
18             if (str[l] == "(" || str[l] == "*") && (str[r] == ")" || str[r] == "*") && isValid(l+1, r-1) == 1 {
19                 memo[l][r] = 1
20                 return 1
21             }
22             
23             for k in l ..< r {
24                 if isValid(l, k) == 1 && isValid(k+1, r) == 1 {
25                     memo[l][r] = 1
26                     return 1
27                 }
28             }
29             
30             memo[l][r] = 0
31             return 0
32         }
33         
34         return isValid(0, s.count - 1) == 1
35     }
36 }

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap