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

概述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 guaran

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 = 011         while(k < s.count)12         {13             if s[k] >= "0" && s[k] <= "9"14             {15                 cnt = cnt*10 + (s[k].ascii - 48)16                 k += 117             }18             else if s[k] == "["19             {20                 k += 121                 var tem:String = DFS(s,&k)22                 for i in 0..<cnt23                 {24                     ans += tem25                     cnt = 026                 }27             }28             else if s[k] == "]"29             {30                 k += 131                 return ans32             }33             else34             {35                 ans.append(s[k])36                 k += 137             }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).unicodeScalars59             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 = 011         var ans = [Character]()12         while i < c.count && c[i] != "]" {13             let iv = c[i].unicodeScalars.first!.value14             if iv<=nv && iv>=zv {15                 num = num*10 + Int(iv-zv)16             } else if c[i] == "[" {17                 i+=118                 let re = de(c,&i)19                 for j in  0..<num {20                     ans += re21                 }22                 num=023                 24             } else {25                 ans.append(c[i])26             }27             i+=128         }29         return ans30     }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).integerValue23         for _ in 1...bound{24             result += tempStr25         }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 result33     }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 true134         case "A"..."Z":135             return true136         default:137             return false138         }139     }140 141     func isHexaAlpha() -> Bool {142         switch self {143         case "a"..."f":144             return true145         case "A"..."F":146             return true147         default:148             return false149         }150     }151 152     func isNumeric() -> Bool {153         switch self {154         case "0"..."9":155             return true156         default:157             return false158         }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 nil168         }169         return Int(unicodeScalar.value) - AsciiValue.zero170     }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 = strItme13 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] + result70         }71        72         return result73     }74     75     func isPurnInt(string: String) -> Bool {76         let scan: Scanner = Scanner(string: string)77         var val:Int = 078         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 = 014             } else if char == "]" {15                 var wordToAdd = String(repeating: words.popLast()!,count: nums.popLast()!)16                 if words.count > nums.count {17                     wordToAdd = words.popLast()! + wordToAdd18                 }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 + num27             } 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 result37     }38 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode394. 字符串解码 | Decode String全部内容，希望文章能够帮你解决[Swift]LeetCode394. 字符串解码 | Decode String所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。