[Swift]LeetCode833.字符串中的查找与替换|FindAndReplaceinString

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

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

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

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

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

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

To some string S, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).

Each replacement operation has 3parameters: a starting index i, a source word x and a target word y. The rule is that if x starts at position i in the originalstring S, then we will replace that occurrence of x with y. If not, we do nothing.

For example, if we have S = "abcd" and we have some replacement operation i = 2, x = "cd", y = "ffff", then because "cd" starts at position 2 in the original string S, we will replace it with "ffff".

Using another example on S = "abcd", if we have both the replacement operation i = 0, x = "ab", y = "eee", as well as another replacement operation i = 2, x = "ec", y = "ffff", this second operation does nothing because in the original string S[2] = 'c', which doesn't match x[0] = 'e'.

All these operations occur simultaneously. It's guaranteed that there won't be any overlap in replacement: for example, S = "abc", indexes = [0, 1], sources = ["ab","bc"] is not a valid test case.

Example 1:

Input: S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
Output: "eeebffff"
Explanation: "a" starts at index 0 in S, so it's replaced by "eee".
"cd" starts at index 2 in S, so it's replaced by "ffff".

Example 2:

Input: S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation: "ab" starts at index 0 in S, so it's replaced by "eee". 
"ec" doesn't starts at index 2 in the original S, so we do nothing.

Notes:

0 <= indexes.length = sources.length = targets.length <= 100
0 < indexes[i] < S.length <= 1000
All characters in given inputs are lowercase letters.

对于某些字符串 S，我们将执行一些替换操作，用新的字母组替换原有的字母组（不一定大小相同）。

每个替换操作具有 3 个参数：起始索引 i，源字 x 和目标字 y。规则是如果 x 从原始字符串 S 中的位置 i 开始，那么我们将用 y 替换出现的 x。如果没有，我们什么都不做。

举个例子，如果我们有 S = “abcd” 并且我们有一些替换操作 i = 2，x = “cd”，y = “ffff”，那么因为 “cd” 从原始字符串 S 中的位置 2 开始，我们将用 “ffff”替换它。

再来看 S = “abcd” 上的另一个例子，如果我们有替换操作 i = 0，x = “ab”，y = “eee”，以及另一个替换操作 i = 2，x = “ec”，y = “ffff”，那么第二个操作将不执行任何操作，因为原始字符串中 S[2] = 'c'，与 x[0] = 'e' 不匹配。

所有这些操作同时发生。保证在替换时不会有任何重叠： S = "abc", indexes = [0, 1], sources = ["ab","bc"] 不是有效的测试用例。

示例 1：

输入：S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
输出："eeebffff"
解释：
"a" 从 S 中的索引 0 开始，所以它被替换为 "eee"。
"cd" 从 S 中的索引 2 开始，所以它被替换为 "ffff"。

示例 2：

输入：S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
输出："eeecd"
解释：
"ab" 从 S 中的索引 0 开始，所以它被替换为 "eee"。
"ec" 没有从原始的 S 中的索引 2 开始，所以它没有被替换。

提示：

0 <= indexes.length = sources.length = targets.length <= 100
0 < indexes[i] < S.length <= 1000
给定输入中的所有字符都是小写字母。

36ms

 1 final class Solution {
 2     func findReplaceString(_ S: String, _ indexes: [Int], _ sources: [String], _ targets: [String]) -> String {
 3         var dict: [Int: (String, String)] = Dictionary(uniqueKeysWithValues: zip(indexes, zip(sources, targets)) )
 4         var indexes = indexes.sorted(by: >)
 5         var S = Array(S)
 6         var res = S
 7         for index in indexes {
 8             let val = dict[index]!
 9             let source = Array(val.0)
10             let target = Array(val.1)
11             if hasOccurence(S, source, index) {
12                 res.replaceSubrange(index..<(index &+ source.count), with: target)
13             }
14         }
15         return String(res)
16     }
17     
18     @inline(__always) private func hasOccurence(_ S: [Character], _ source: [Character], _ index: Int) -> Bool {
19         for i in index..<(index + source.count) {
20             if i >= S.count { return false }
21             if S[i] != source[i - index] { return false }
22         }
23         return true
24     }
25 }

40ms

 1 class Solution {    
 2     struct StringReplaceIndex: Comparable {
 3         let index: Int
 4         let source: String
 5         let target: String
 6 
 7         static func < (lhs: StringReplaceIndex, rhs: StringReplaceIndex) -> Bool {
 8             return lhs.index < rhs.index
 9         }
10     }
11 
12     func findReplaceString(_ S: String, _ indices: [Int], _ sources: [String], _ targets: [String]) -> String {
13         // build the replace indices in sorted order
14         var replaceIndices = [StringReplaceIndex]()
15         for i in 0..<indices.count {
16             replaceIndices.append(StringReplaceIndex(index: indices[i], source: sources[i], target: targets[i]))
17         }
18         replaceIndices.sort()
19 
20         var result = [String]()
21 
22         // need to handle the substring when the indices doesn't start from 0
23         if replaceIndices[0].index != 0 {
24             let subString = S.subString(from: 0, to: replaceIndices[0].index - 1)
25             result.append(subString)
26         }
27 
28         for i in 0..<replaceIndices.count {
29             let startIndex = replaceIndices[i].index
30             let endIndex = ((i+1) < replaceIndices.count) ? replaceIndices[i+1].index - 1 : S.count - 1
31             var subString = S.subString(from: startIndex, to: endIndex)
32             if subString.hasPrefix(replaceIndices[i].source) {
33                 subString.removeFirst(replaceIndices[i].source.count)
34                 subString = replaceIndices[i].target + subString
35             }
36             result.append(subString)
37         }
38         return result.reduce("", +)
39     }        
40 }
41     
42 extension String {
43 
44     subscript(i: Int) -> Character {
45         get {
46             return self[index(startIndex, offsetBy: i)]
47         }
48     }
49 
50     func subString(from: Int, to: Int) -> String {
51         guard from <= to else {
52             return ""
53         }
54 
55         let startIndex = self.index(self.startIndex, offsetBy: from)
56         let endIndex = self.index(self.startIndex, offsetBy: to)
57         return String(self[startIndex...endIndex])
58     }
59 
60     func subString(from: Int) -> String {
61         let startIndex = self.index(self.startIndex, offsetBy: from)
62         return String(self.suffix(from: startIndex))
63     }
64 
65     func asciiValues() -> [Int] {
66         return Array(self.utf16).map { Int($0) }
67     }
68 
69     mutating func lTrim(_ regex: String = "^\\s+") {
70         if let trailingSpacesRange = self.range(of: regex, options: .regularExpression) {
71             self.replaceSubrange(trailingSpacesRange, with: "")
72         }
73     }
74 
75     mutating func rTrim(_ regex: String = "\\s+$") {
76         if let trailingSpacesRange = self.range(of: regex, options: .regularExpression) {
77             self.replaceSubrange(trailingSpacesRange, with: "")
78         }
79     }
80 
81     func stringByReplacingAt(_ index: Int, with ch: Character) -> String {
82         var chars = Array(self)
83         chars[index] = ch
84         let modifiedString = String(chars)
85         return modifiedString
86     }
87 }

48ms

 1 class Solution {
 2     private struct ConfirmedReplacement {
 3         let start: String.Index
 4         let end: String.Index
 5         let target: String
 6     }
 7     
 8     func findReplaceString(_ S: String, _ indexes: [Int], _ sources: [String], _ targets: [String]) -> String {
 9         var confirmedTargets: [ConfirmedReplacement] = []
10         //1. confirm
11         for i in 0..<indexes.count {
12             let start = S.index(S.startIndex, offsetBy: indexes[i])
13             let source = sources[i]
14             let end = S.index(start, offsetBy: source.count)
15             let target = targets[i]
16             if S[start..<end] != source {
17                 continue
18             }
19             let confirmed = ConfirmedReplacement(start: start, end: end, target: target)
20             confirmedTargets.append(confirmed)
21         }
22         //2. sort confirmed range
23         confirmedTargets = confirmedTargets.sorted(by: { (lhs, rhs) -> Bool in
24             return rhs.start > lhs.start
25         })
26         //3. fill string
27         var strFragments: [String] = []
28         var index = S.startIndex
29         for target in confirmedTargets {
30             strFragments.append(String(S[index..<target.start]))
31             strFragments.append(target.target)
32             index = target.end
33         }
34         strFragments.append(String(S[index..<S.endIndex]))
35         return strFragments.joined()
36     }
37 }

Runtime: 60 ms

Memory Usage: 19.7 MB

 1 class Solution {
 2     func findReplaceString(_ S: String, _ indexes: [Int], _ sources: [String], _ targets: [String]) -> String {
 3         var S = S
 4         var v:[[Int]] = [[Int]]()
 5         for i in 0..<indexes.count
 6         {
 7             v.append([indexes[i], i])
 8         }
 9         v.sort(by:{(a:[Int],b:[Int]) -> Bool in 
10                    if a[0] == b[0]
11                    {
12                        return a[1] >= b[1]
13                    }
14                    else
15                    {
16                        return a[0] > b[0]
17                    }
18                   })
19         for a in v
20         {
21             var i:Int = a.first!
22             var str:String = sources[a[1]]
23             var t:String = targets[a[1]]
24             if S.subString(i, str.count) == str
25             {
26                 S = S.subString(0, i) + t + S.subString(i + str.count)
27             }
28         }
29         return S
30     }
31 }
32 
33 extension String {
34     // 截取字符串：从index到结束处
35     // - Parameter index: 开始索引
36     // - Returns: 子字符串
37     func subString(_ index: Int) -> String {
38         let theIndex = self.index(self.endIndex, offsetBy: index - self.count)
39         return String(self[theIndex..<endIndex])
40     }
41     
42     // 截取字符串：指定索引和字符数
43     // - begin: 开始截取处索引
44     // - count: 截取的字符数量
45     func subString(_ begin:Int,_ count:Int) -> String {
46         let start = self.index(self.startIndex, offsetBy: max(0, begin))
47         let end = self.index(self.startIndex, offsetBy:  min(self.count, begin + count))
48         return String(self[start..<end]) 
49     }
50 }