[Swift]LeetCode241.为运算表达式设计优先级|DifferentWaystoAddParentheses ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

Input: "2-1-1"
Output: [0, 2]
Explanation: 
((2-1)-1) = 0 
(2-(1-1)) = 2

Example 2:

Input: "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Explanation: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:

输入: "2-1-1"
输出: [0, 2]
解释: 
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2:

输入: "2*3-4*5"
输出: [-34, -14, -10, -10, 10]
解释: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

12ms

 1 class Solution {
 2     
 3     var c = [String : [Int]]()
 4     func diffWaysToCompute(_ input: String) -> [Int] {
 5         let sp = Array(input)
 6         let result = getResult(sp)
 7         return result
 8     }
 9     
10     func getResult(_ s:[Character]) -> [Int] {
11         if let arr = c[String(s)] {
12             return arr
13         }
14         var ans = [Int]()
15         for i in 0 ..< s.count {
16             if s[i] == "+" || s[i] == "-" || s[i] == "*" {
17                 let left = Array(s.prefix(upTo: i))
18                 let right = Array(s.suffix(from: i+1))
19                 let l = getResult(left)
20                 let r = getResult(right)
21                 
22                 for a in l {
23                     for b in r {
24                         if s[i] == "+" {
25                             ans.append(a + b)
26                         } else if s[i] == "-" {
27                             ans.append(a - b)
28                         } else if s[i] == "*" {
29                             ans.append(a * b)
30                         }
31                     }
32                 }                
33             }
34         }
35         if ans.isEmpty {
36             var val : Int = 0
37             for dig in s {
38                 val = val * 10 + Int(dig.unicodeScalars.first!.value - "0".unicodeScalars.first!.value)
39             }
40             ans.append(val)
41         }
42         c[String(s)] = ans
43         return ans
44     }
45 }

24ms

 1 class Solution {
 2     func diffWaysToCompute(_ input: String) -> [Int] {
 3 
 4         var res = [Int]()
 5         for (i, c) in input.enumerated(){
 6             if c == "+" || c == "-" || c == "*" {
 7                 var left = diffWaysToCompute(input.substring(0, i))
 8                 var right = diffWaysToCompute(input.substring(i+1))
 9                 for j in left.indices {
10                     for k in right.indices {
11                         if c == "+" { res.append(left[j] + right[k])}
12                         if c == "-" { res.append(left[j] - right[k])}
13                         if c == "*" { res.append(left[j] * right[k])}
14                     }
15                 }
16             }
17         }
18                
19         if res.isEmpty { res.append(Int(input)!) }
20         return res
21     }
22 }
23 
24 extension String {
25     func substring(_ i: Int, _ len: Int = -1) -> String {
26         var startInd = index(startIndex, offsetBy: i)
27         var endInd = endIndex
28         if len != -1 { endInd = index(startIndex, offsetBy: i+len) }
29         return String(self[startInd..<endInd])
30     }
31 }

24ms

 1 class Solution {
 2     func diffWaysToCompute(_ input: String) -> [Int] {
 3         let sarr = Array(input)
 4         var res = [Int]()
 5         for i in 0..<sarr.count {
 6             let c = sarr[i]
 7             if c == "+" || c == "-" || c == "*" {
 8                 let res1 = diffWaysToCompute(String(sarr[0..<i]))
 9                 let res2 = diffWaysToCompute(String(sarr[i+1..<sarr.count]))
10                 for r1 in res1 {
11                     for r2 in res2 {
12                         if c == "+" {
13                             res.append(r1 + r2)
14                         }else if c == "-" {
15                             res.append(r1 - r2)
16                         }else if c == "*" {
17                             res.append(r1 * r2)
18                         }
19                     }
20                 }
21             }
22         }
23         if res.isEmpty {
24             res.append(Int(input)!)
25         }
26         return res
27     }
28 }

44ms

 1 class Solution {
 2     let operators : [Character] = ["+","-","*"]
 3     func diffWaysToCompute(_ input: String) -> [Int] {
 4         var result : [Int] = []
 5         var index : String.Index = input.startIndex
 6         while index != input.endIndex  {
 7             if operators.contains(input[index]){
 8                 let resultLeft = diffWaysToCompute(String(input[..<index]))
 9                 let resultRight = diffWaysToCompute(String(input[input.index(after: index)...]))
10                 for leftNum in resultLeft {
11                     for rightNum in resultRight {
12                         switch input[index] {
13                         case "+":
14                             result.append(leftNum+rightNum)
15                         case "-":
16                             result.append(leftNum-rightNum)
17                         case "*":
18                             result.append(leftNum*rightNum)
19                         default:
20                             break
21                         }
22                     }
23                 }
24             }
25             index = input.index(after: index)
26         }
27         if result.isEmpty {
28             result.append(Int(input) ?? 0)
29         }
30         
31         return result
32     }
33 }