[Swift]LeetCode784.字母大小写全排列|LetterCasePermutation

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

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

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

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

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

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

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

Examples:
Input: S = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4"
Output: ["3z4", "3Z4"]

Input: S = "12345"
Output: ["12345"]

Note:

S will be a string with length between 1 and 12.
S will consist only of letters or digits.

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例:
输入: S = "a1b2"
输出: ["a1b2", "a1B2", "A1b2", "A1B2"]

输入: S = "3z4"
输出: ["3z4", "3Z4"]

输入: S = "12345"
输出: ["12345"]

注意：

S 的长度不超过12。
S 仅由数字和字母组成。

96ms

 1 class Solution {
 2     func letterCasePermutation(_ S: String) -> [String] {
 3         let arr = Array(S.uppercased().cString(using: .ascii)!)
 4         var ans = [String]()
 5         ans.reserveCapacity(1024)
 6         
 7         var tmp = [CChar](repeating: 0, count: arr.count + 1)
 8         
 9         func step(_ tmp: inout [CChar], _ idx: Int) {
10             if idx == arr.count - 1 {
11                 ans.append(String(cString: tmp))
12             } else if arr[idx] < 65 {
13                 tmp[idx] = arr[idx]
14                 step(&tmp, idx + 1)
15             } else {
16                 tmp[idx] = arr[idx]
17                 step(&tmp, idx + 1)
18                 tmp[idx] = arr[idx] + 32
19                 step(&tmp, idx + 1)
20             }            
21         }
22         
23         step(&tmp, 0)        
24         return ans
25     }
26 }

112ms

 1 class Solution {
 2     func letterCasePermutation(_ S: String) -> [String] {
 3 var list: [String] = []
 4     if S.isEmpty {
 5         return [S]
 6     }
 7     
 8     if let _ = Int(S) {
 9         return [S]
10     }
11     var source = S
12     for _ in 0..<source.count {
13         let c = source.removeFirst()
14         letterCaseRec(c: c, list: &list)
15     }    
16         return list
17     }
18     
19     
20     func letterCaseRec(c: Character, list: inout [String]) {
21     
22     var opp:String? = nil
23     if list.isEmpty {
24         list.append(String(c))
25         if let _ = Int(String(c)) {
26         } else {
27             opp = String(c) == String(c).capitalized ? String(c).lowercased() :  String(c).capitalized
28              list.append(opp!)
29         }
30        return
31     }
32     
33     if let _ = Int(String(c)) {
34         for x in 0..<list.count {
35             list[x].append(c)
36         }
37     } else {
38         opp = String(c) == String(c).capitalized ? String(c).lowercased() :  String(c).capitalized
39         let size = list.count
40         for x in 0..<size {
41             let current = list[x]
42             list.append(current + opp!)
43             list[x].append(c)          
44         }
45     }
46   }    
47 }

116ms

 1 class Solution {
 2     
 3      func letterCasePermutation(_ S: String) -> [String] {
 4         var result = [String]()
 5         letterCasePermutation(S, 0, "", &result)
 6         return result
 7     }
 8     
 9     func letterCasePermutation(_ S: String, _ index: Int, _ currentS: String, _ result: inout [String]) {
10         if index >= S.count {
11             result.append(currentS)
12             return
13         }
14     
15         let char = S[S.index(S.startIndex, offsetBy: index)]
16         letterCasePermutation(S, index+1, (currentS+String(char).lowercased()), &result)
17         if let c = char.unicodeScalars.first, CharacterSet.letters.contains(c) {
18             letterCasePermutation(S, index+1, (currentS+String(char).uppercased()), &result)
19         }
20     }
21 }

124ms

 1 class Solution {
 2     func letterCasePermutation(_ S: String) -> [String] {
 3         var cur = String(), res = [String]()
 4         var sChars = Array(S)
 5         recursion(&sChars, 0, &res)
 6         return res
 7     }
 8     
 9     private func recursion(_ sChars: inout [Character], _ i: Int, _ res: inout [String]) {
10         if i == sChars.count {
11             res.append(String(sChars))
12             return
13         }
14         
15         recursion(&sChars, i + 1, &res)
16     
17         if sChars[i] >= "0" && sChars[i] <= "9" { return } // it a number
18         sChars[i] = toggleCase(sChars[i])
19         recursion(&sChars, i + 1, &res)
20         sChars[i] = toggleCase(sChars[i])
21         
22     }
23     
24     private func toggleCase(_ char: Character) -> Character {
25         let s = String(char)
26         if s.uppercased() == s {
27             return Character(s.lowercased())
28         } else {
29             return Character(s.uppercased())
30         }
31     }
32 }

128ms

 1 class Solution {
 2     func letterCasePermutation(_ S: String) -> [String] {
 3         var result = [String]()
 4         result.append(S.lowercased())
 5         if Int(S) != nil {
 6             return result
 7         }
 8         for (k,i) in S.enumerated() {
 9             if(Int(String(i)) != nil) {
10                 continue
11             }
12             for j in 0..<result.count {
13                 var entry = Array(result[j])
14                 entry[k] = Character(String(entry[k]).uppercased())
15                 result.append(String(entry))
16             }
17         
18         }
19         return result
20     }
21 }

132ms

 1 class Solution {
 2     func patternToString(_ pattern: String, _ source: String) -> String {
 3         var result = ""
 4         var posInPattern = 0
 5         let upperSource = source.uppercased()
 6         for i in 0..<source.count {
 7             let s = source[source.index(source.startIndex, offsetBy: i)]
 8             if s >= "a" && s <= "z" {
 9                 let S = upperSource[upperSource.index(upperSource.startIndex, offsetBy: i)]
10                 result.append(pattern[pattern.index(pattern.startIndex, offsetBy: posInPattern)] == "0" ? s : S)
11                 posInPattern += 1
12             } else {
13                 result.append(s)
14             }
15         }
16         return result
17     }
18     
19     func letterCasePermutation(_ S: String) -> [String] {
20         let s = S.lowercased()
21         var count = 1
22         var bitCount = 0
23         for c in s {
24             if c >= "a" && c <= "z" {
25                 count *= 2
26                 bitCount += 1
27             }
28         }
29         
30         guard bitCount > 0 else {
31             return [S]
32         }
33         
34         var result = [String]()
35         for i in 0..<count {
36             var binStr = String(i, radix: 2)
37             if binStr.count < bitCount {
38                 binStr = String(repeating: "0", count: bitCount - binStr.count) + binStr
39             }
40             result.append(patternToString(binStr, s))
41         }
42         return result
43     }
44 }

140ms

 1 class Solution {
 2     func letterCasePermutation(_ S: String) -> [String] {
 3         var result = [String]()
 4         dfs(S, 0, "", &result, S.count)
 5         return result
 6     }
 7     
 8     func dfs(_ S: String, 
 9              _ index: Int,
10              _ currentS: String, 
11              _ result: inout [String],
12              _ lengthS: Int) {
13         if index >= lengthS {
14             result.append(currentS)
15             return
16         }
17     
18         let char = S[S.index(S.startIndex, offsetBy: index)]
19         dfs(S, 
20             index+1, 
21             (currentS+String(char).lowercased()),
22             &result,
23             lengthS)
24         if let c = char.unicodeScalars.first, CharacterSet.letters.contains(c) {
25             dfs(S, 
26                 index+1,
27                 (currentS+String(char).uppercased()),
28                 &result,
29                 lengthS)
30         }
31     }        
32 }

180ms

 1 class Solution {
 2     func letterCasePermutation(_ S: String) -> [String] {
 3         var res: [[String]] = [[]]
 4 
 5         for char in S {
 6             if isAlpha(char) {
 7                 for i in 0..<res.count {
 8                     res.append(res[i])
 9                     res[i].append(String(char).lowercased())
10                     res[res.count-1].append(String(char).uppercased())
11                 }
12             } else {
13                 for (i, var s) in res.enumerated() {
14                     s.append(String(char))
15                     res[i] = s
16                 }
17             }
18         }
19 
20         return res.map { $0.joined() }
21     }
22 
23     private func isAlpha(_ char: Character) -> Bool {
24         if let value = char.unicodeScalars.first?.value {
25             if (value > 64 && value < 91) || (value > 96 && value < 123) {
26                 return true;
27             }
28         }
29         return false;
30     }
31 }

Runtime: 196 ms

Memory Usage: 20.5 MB

 1 class Solution {
 2     func letterCasePermutation(_ S: String) -> [String] {
 3         var S = S
 4         var res:[String] = [String]()
 5         helper(&S, 0, &res)
 6         return res
 7     }
 8     
 9     func helper(_ s:inout String,_ pos:Int,_ res:inout [String])
10     {
11         var arrChar:[Character] = Array(s)
12         var arrInt:[Int] = arrChar.map{$0.ascii}
13         if pos == s.count
14         {
15             res.append(s)
16             return
17         }
18         helper(&s, pos + 1, &res)
19         if arrInt[pos] > 57
20         {
21             arrInt[pos] ^= 32;
22             arrChar = arrInt.map{$0.ASCII}
23             s = String(arrChar)
24             helper(&s, pos + 1, &res);
25         }
26     }
27 }
28 
29 //String扩展
30 extension String {        
31     //subscript函数可以检索数组中的值
32     //直接按照索引方式截取指定索引的字符
33     subscript (_ i: Int) -> Character {
34         //读取字符
35         get {return self[index(startIndex, offsetBy: i)]}
36     }
37 }
38 
39 //Character扩展 
40 extension Character  
41 {  
42   //Character转ASCII整数值(定义小写为整数值)
43    var ascii: Int {
44        get {
45            return Int(self.unicodeScalars.first?.value ?? 0)
46        }       
47     }    
48 }
49 
50 //Int扩展
51 extension Int
52 {
53     //Int转Character,ASCII值(定义大写为字符值)
54     var ASCII:Character 
55     {
56         get {return Character(UnicodeScalar(self)!)}
57     }
58 }

232ms

 1 class Solution {
 2     var res = [String]()
 3     func letterCasePermutation(_ S: String) -> [String] {
 4         var wordsArr = [String]()
 5         for c in S{
 6             wordsArr.append(String(c))
 7         }
 8         dps("",wordsArr)
 9         return res
10     }
11     
12     func dps(_ head:String, _ foot:[String]) -> Void{
13         if foot.count == 0{
14             res.append(head)
15             return
16         }
17         var s:String = foot.first!
18         var newfoot = foot
19         newfoot.removeFirst()
20         if s <= "9" {
21             dps(head+s,newfoot)
22         }else{
23             dps(head+String(s.lowercased()),newfoot)
24             dps(head+String(s.uppercased()),newfoot)
25         }
26     }    
27 }

256ms

 1 class Solution {
 2     func letterCasePermutation(_ S: String) -> [String] {
 3         
 4         func isNum( _ s : String) -> Bool {
 5             let scan = Scanner(string: s)
 6             var val : Int = 0
 7             return scan.scanInt(&val) && scan.isAtEnd
 8         }
 9         
10         func char(at i : Int, _ s : String) -> String {
11             return String(s[s.index(s.startIndex, offsetBy: i)])
12         }
13         
14         var source : [String] = []
15         for i in 0 ..< S.count {
16             source.append(char(at: i, S))
17         }
18         var res = [String]()
19         let n = S.count
20         func backTrace(t : Int, src : [String], s :  String) {
21             if t >= n {
22                 res.append(s)
23             } else {
24                 if isNum(source[t]) {
25                     backTrace(t: t+1, src: source, s: s+source[t])
26                     return
27                 }
28                 for i in 0 ... 1 {
29                     if i == 0 { //小写
30                         backTrace(t: t+1, src: source, s: s+source[t].lowercased())
31                         
32                     } else { // i == 1 大写
33                         backTrace(t: t+1, src: source, s: s+source[t].uppercased())
34                     }
35                 }
36             }
37         }
38         backTrace(t: 0, src: source, s: "")
39         return res
40     }
41 }