加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

[Swift]LeetCode394. 字符串解码 | Decode String

发布时间:2020-12-14 05:05:36 所属栏目:百科 来源:网络整理
导读:Given an encoded string,return it‘s decoded string. The encoding rule is:? k[encoded_string] ,where the? encoded_string inside the square brackets is being repeated exactly? k ?times. Note that? k is guaranteed to be a positive integer. Y

Given an encoded string,return it‘s decoded string.

The encoding rule is:?k[encoded_string],where the?encoded_stringinside the square brackets is being repeated exactly?k?times. Note that?kis guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces,square brackets are well-formed,etc.

Furthermore,you may assume that the original data does not contain any digits and that digits are only for those repeat numbers,?k. For example,there won‘t be input like?3a?or?2[4].

Examples:

s = "3[a]2[bc]",return "aaabcbc".
s = "3[a2[c]]",return "accaccacc".
s = "2[abc]3[cd]ef",return "abcabccdcdcdef".

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为:?k[encoded_string],表示其中方括号内部的?encoded_string?正好重复?k?次。注意?k?保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数?k,例如不会出现像?3a?或?2[4]?的输入。

示例:

s = "3[a]2[bc]",返回 "aaabcbc".
s = "3[a2[c]]",返回 "accaccacc".
s = "2[abc]3[cd]ef",返回 "abcabccdcdcdef".

12ms
 1 class Solution {
 2     func decodeString(_ s: String) -> String {
 3         var k:Int = 0
 4         return DFS(s,&k)        
 5     }
 6     
 7     func DFS(_ s:String,_ k:inout Int) -> String
 8     {
 9         var ans:String = String()
10         var cnt:Int = 0
11         while(k < s.count)
12         {
13             if s[k] >= "0" && s[k] <= "9"
14             {
15                 cnt = cnt*10 + (s[k].ascii - 48)
16                 k += 1
17             }
18             else if s[k] == "["
19             {
20                 k += 1
21                 var tem:String = DFS(s,&k)
22                 for i in 0..<cnt
23                 {
24                     ans += tem
25                     cnt = 0
26                 }
27             }
28             else if s[k] == "]"
29             {
30                 k += 1
31                 return ans
32             }
33             else
34             {
35                 ans.append(s[k])
36                 k += 1
37             }
38         }
39         return ans        
40     }
41 }
42 
43 extension String {        
44     //subscript函数可以检索数组中的值
45     //直接按照索引方式截取指定索引的字符
46     subscript (_ i: Int) -> Character {
47         //读取字符
48         get {return self[index(startIndex,offsetBy: i)]}
49     }
50 }
51 
52 //Character扩展方法  
53 extension Character  
54 {  
55   //属性:ASCII整数值(定义小写为整数值)
56    var ascii: Int {
57         get {
58             let s = String(self).unicodeScalars
59             return Int(s[s.startIndex].value)
60         }
61     }
62 }

12ms

 1 class Solution {
 2     func decodeString(_ s: String) -> String {
 3         var i = 0
 4         return String(de(Array(s),&i))
 5     }
 6     
 7     let zv = "0".unicodeScalars.first!.value,nv = "9".unicodeScalars.first!.value
 8     
 9     func de(_ c: [Character],_ i: inout Int) -> [Character]{
10         var num = 0
11         var ans = [Character]()
12         while i < c.count && c[i] != "]" {
13             let iv = c[i].unicodeScalars.first!.value
14             if iv<=nv && iv>=zv {
15                 num = num*10 + Int(iv-zv)
16             } else if c[i] == "[" {
17                 i+=1
18                 let re = de(c,&i)
19                 for j in  0..<num {
20                     ans += re
21                 }
22                 num=0
23                 
24             } else {
25                 ans.append(c[i])
26             }
27             i+=1
28         }
29         return ans
30     }
31 }

12ms

 1 import Foundation
 2 class Solution {
 3     func decodeString(_ s: String) -> String {
 4     var numOfLeft:Int = 0;
 5     var tempStack:[Character] = [Character]();
 6     var resultString:String = String();
 7     
 8     func toStringWhenRight()->String{//遇到不是数字就停止
 9         var tempStr = ""
10         var tempNum = ""
11         var result = ""
12         while tempStack[tempStack.count-1] != "[" {
13             let temp = String.init(tempStack.popLast()!)
14             tempStr = temp + tempStr;
15         }
16         tempStack.removeLast()
17         while (tempStack.count>0&&tempStack[tempStack.count-1]>="0"&&tempStack[tempStack.count-1]<="9"){
18             let temp = String.init(tempStack.popLast()!)
19             tempNum = temp + tempNum;
20             // print(tempStack.count)
21         }
22         let bound = (tempNum as NSString).integerValue
23         for _ in 1...bound{
24             result += tempStr
25         }
26         //读取其余的字母
27         while (tempStack.count>0&&tempStack[tempStack.count-1]>="a"&&tempStack[tempStack.count-1]<="z"){
28             let str = String.init(tempStack.popLast()!)
29             result =  str + result;
30         }
31         numOfLeft -= 1;
32         return result
33     }
34     for char in s{
35         if(char == "["){
36             numOfLeft+=1;
37             tempStack.append(char);
38         }else if(char=="]"){
39             if(numOfLeft == 1){
40                 resultString += toStringWhenRight();
41             }else if(numOfLeft > 1){
42                 tempStack.append(contentsOf: toStringWhenRight());
43             }else{fatalError("something strange hanppens")}
44         }else{
45             tempStack.append(char);
46         }
47     }
48     resultString += String.init(tempStack);
49     return resultString;
50   }
51 }

16ms

  1 class Solution {
  2    
  3     func decodeString(_ str: String) -> String {
  4         // stores the ascii values of the characters
  5         var stack: [String] = []
  6 
  7         // used to store the formed number of times
  8         var number: Int? = 0
  9 
 10         // running index in str
 11         var index = 0
 12         while index < str.count {
 13             let ch = str[index]
 14 
 15             if ch.isNumeric() {
 16                 number = (number ?? 0) * 10 + ch.numericValue()!
 17             } else if ch == "[" {
 18                 if let number = number {
 19                     stack.append(String(number))
 20                 }
 21                 number = nil
 22                 stack.append(String(ch))
 23             } else if ch == "]" {
 24                 number = nil
 25                 // decode the string and push on to stack
 26                 var values = [String]()
 27                 var times = 0
 28                 while let top = stack.last {
 29                     if top == "[" {
 30                         // removes the square bracket
 31                         stack.removeLast()
 32 
 33                         // remove the number
 34                         times = Int(stack.removeLast())!
 35 
 36                         break
 37                     } else {
 38                         values.insert(stack.removeLast(),at: 0)
 39                     }
 40                 }
 41 
 42                 stack.append(decodeString(times,values))
 43             } else {
 44                 number = nil
 45                 // any other character
 46                 stack.append(String(ch))
 47             }
 48 
 49             index += 1
 50         }
 51 
 52         let result = stack.reduce("") { $0 + $1 }
 53         return result
 54     }
 55 
 56     func decodeString(_ times: Int,_ values: [String]) -> String {
 57         let str = values.reduce("",+)
 58         var result = ""
 59         for _ in 0..<times {
 60             result += str
 61         }
 62 
 63         return result
 64     }
 65         
 66 }
 67         
 68 extension String {
 69     
 70     subscript (i: Int) -> Character {
 71         return self[index(startIndex,offsetBy: i)]
 72     }
 73     
 74     func subString(from: Int,to: Int) -> String {
 75         guard from <= to else {
 76             return ""
 77         }
 78         
 79         let startIndex = self.index(self.startIndex,offsetBy: from)
 80         let endIndex = self.index(self.startIndex,offsetBy: to)
 81         return String(self[startIndex...endIndex])
 82     }
 83     
 84     func subString(from: Int) -> String {
 85         let startIndex = self.index(self.startIndex,offsetBy: from)
 86         return String(self.suffix(from: startIndex))
 87     }
 88     
 89     func asciiValues() -> [Int] {
 90         return Array(self.utf16).map { Int($0) }
 91     }
 92     
 93     mutating func lTrim() {
 94         if let trailingSpacesRange = self.range(of: "^s+",options: .regularExpression) {
 95             self.replaceSubrange(trailingSpacesRange,with: "")
 96         }
 97     }
 98     
 99     mutating func rTrim() {
100         if let trailingSpacesRange = self.range(of: "s+$",options: .regularExpression) {
101             self.replaceSubrange(trailingSpacesRange,with: "")
102         }
103     }
104     
105 }
106 
107 struct AsciiValue {
108     static let zero = Int(Character("0").unicodeScalars.first?.value ?? 0)
109     static let nine = Int(Character("9").unicodeScalars.first?.value ?? 0)
110     static let lowercaseCaseA = Int(Character("a").unicodeScalars.first?.value ?? 0)
111     static let lowercaseCaseZ = Int(Character("z").unicodeScalars.first?.value ?? 0)
112     static let capitalCaseA = Int(Character("A").unicodeScalars.first?.value ?? 0)
113     static let capitalCaseZ = Int(Character("Z").unicodeScalars.first?.value ?? 0)
114     static let openBracket = Int(Character("(").unicodeScalars.first?.value ?? 0)
115     static let closeBracket = Int(Character(")").unicodeScalars.first?.value ?? 0)
116     static let openSquareBracket = Int(Character("[").unicodeScalars.first?.value ?? 0)
117     static let closeSquareBracket = Int(Character("]").unicodeScalars.first?.value ?? 0)
118     static let openCurlyBracket = Int(Character("{").unicodeScalars.first?.value ?? 0)
119     static let closeCurlyBracket = Int(Character("}").unicodeScalars.first?.value ?? 0)
120     static let exponent = Int(Character("e").unicodeScalars.first?.value ?? 0)
121     static let plus = Int(Character("+").unicodeScalars.first?.value ?? 0)
122     static let minus = Int(Character("-").unicodeScalars.first?.value ?? 0)
123     static let star = Int(Character("*").unicodeScalars.first?.value ?? 0)
124     static let forwardSlash = Int(Character("/").unicodeScalars.first?.value ?? 0)
125     static let decimal = Int(Character(".").unicodeScalars.first?.value ?? 0)
126 }
127 
128 extension Character {
129 
130     func isAlpha() -> Bool {
131         switch self {
132         case "a"..."z":
133             return true
134         case "A"..."Z":
135             return true
136         default:
137             return false
138         }
139     }
140 
141     func isHexaAlpha() -> Bool {
142         switch self {
143         case "a"..."f":
144             return true
145         case "A"..."F":
146             return true
147         default:
148             return false
149         }
150     }
151 
152     func isNumeric() -> Bool {
153         switch self {
154         case "0"..."9":
155             return true
156         default:
157             return false
158         }
159     }
160 
161     func isAlphaNumeric() -> Bool {
162         return isAlpha() || isNumeric()
163     }
164 
165     func numericValue() -> Int? {
166         guard let unicodeScalar = unicodeScalars.first else {
167             return nil
168         }
169         return Int(unicodeScalar.value) - AsciiValue.zero
170     }
171 
172     var asciiValue: Int {
173         return Int(self.unicodeScalars.first!.value)
174     }
175 }

20ms

 1 class Solution {
 2     func decodeString(_ s: String) -> String {
 3         var strArr = [String]()
 4         var numIndex = 0
 5         
 6         for i in 0..<s.count {
 7             var strItmeIndex = s.index(s.endIndex,offsetBy: -(i + 1))
 8             var strItme = String.init(s[strItmeIndex])
 9             if strItme != "["{
10 
11                 if self.isPurnInt(string: strItme){
12                     var numStr:String = strItme
13 
14                     while  self.isPurnInt(string: strArr.last!){
15                         numStr =  numStr + strArr.last!
16                         strArr.remove(at: strArr.count - 1)
17                     }
18                     if i != s.count - 1{
19                         strArr.append(numStr)
20                     }else{
21                         var strItmeInt:Int = Int(numStr)!
22                         var strNew:String = ""
23                         for j in 0..<strItmeInt{
24                             strNew = strNew + strArr.last!;
25                         }
26                         strArr.remove(at: strArr.count - 1)
27                         strArr.append(strNew)
28                     }
29                     
30                     
31                 }else{
32                     if strArr.count > 0 && self.isPurnInt(string: strArr.last!) {
33                         var strItmeInt:Int = Int(strArr.last!)!
34                         strArr.remove(at: strArr.count - 1)
35                         var strNew:String = ""
36                         for j in 0..<strItmeInt{
37                             strNew = strNew + strArr.last!;
38                         }
39                       strArr.remove(at: strArr.count - 1)
40                       strArr.append(strNew)
41                     }
42                     strArr.append(strItme)
43                 }
44             }else{
45         
46                 var strNew:String = ""
47                 
48                 if strArr.count > 0 && self.isPurnInt(string: strArr.last!) {
49                     var strItmeInt:Int = Int(strArr.last!)!
50                     strArr.remove(at: strArr.count - 1)
51                     for j in 0..<strItmeInt{
52                         strNew = strNew + strArr.last!;
53                     }
54                     strArr.remove(at: strArr.count - 1)
55                     strArr.append(strNew)
56                 }
57                 strNew = ""
58             
59                 while strArr.last != "]"{
60                     strNew = strNew + strArr.last!;
61                     strArr.remove(at: strArr.count - 1)
62                 }
63                 strArr.remove(at: strArr.count - 1)
64                 strArr.append(strNew)
65             }
66         }
67         var result:String = ""
68         for k in 0..<strArr.count{
69             result =  strArr[k] + result
70         }
71        
72         return result
73     }
74     
75     func isPurnInt(string: String) -> Bool {
76         let scan: Scanner = Scanner(string: string)
77         var val:Int = 0
78         return scan.scanInt(&val) && scan.isAtEnd        
79     }
80 }

20ms

 1 class Solution {
 2     func decodeString(_ s: String) -> String {
 3         var nums = [Int]()
 4         var words = [String]()
 5         let chars = Array(s)
 6         var curNum = 0
 7         var result = ""
 8         
 9         for char in s {
10             if char == "[" {
11                 nums.append(curNum)
12                 words.append("")
13                 curNum = 0
14             } else if char == "]" {
15                 var wordToAdd = String(repeating: words.popLast()!,count: nums.popLast()!)
16                 if words.count > nums.count {
17                     wordToAdd = words.popLast()! + wordToAdd
18                 }
19                 
20                 if let prevWord = words.popLast() {
21                     words.append(prevWord + wordToAdd)
22                 } else {
23                     result.append(contentsOf: wordToAdd)
24                 }
25             } else if let num = Int(String(char)) {
26                 curNum = curNum * 10 + num
27             } else {
28                 if nums.count == 0 {
29                     result.append(char)
30                 } else {
31                     let prevWord = words.popLast() ?? ""
32                     words.append(prevWord + String(char))
33                 }
34             }
35         }        
36         return result
37     }
38 }

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读