[Swift]LeetCode833. 字符串中的查找与替换 | Find And Replace in String
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10576043.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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 <= 1000 < 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 <= 1000 < 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 }