[Swift]LeetCode833. 字符串中的查找与替换 | Find And Replace in String-白红宇

[Swift]LeetCode833. 字符串中的查找与替换 | Find And Replace in String

阅读量：4915 次

发布时间：2019-06-11

本文共 8534 字，大约阅读时间需要 28 分钟。

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

➤微信公众号：山青咏芝（shanqingyongzhi）

➤博客园地址：山青咏芝（）

➤GitHub地址：

➤原文地址：

➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。

➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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 true24     }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 order14         var replaceIndices = [StringReplaceIndex]()15         for i in 0..
     
      < replaceIndices.count) ? replaceIndices[i+1].index - 1 : S.count - 131             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 + subString35             }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] = ch84         let modifiedString = String(chars)85         return modifiedString86     }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. confirm11         for i in 0..
     
       Bool in24             return rhs.start > lhs.start25         })26         //3. fill string27         var strFragments: [String] = []28         var index = S.startIndex29         for target in confirmedTargets {30             strFragments.append(String(S[index..

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..
      
        Bool in 10                    if a[0] == b[0]11                    {12                        return a[1] >= b[1]13                    }14                    else15                    {16                        return a[0] > b[0]17                    }18                   })19         for a in v20         {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) == str25             {26                 S = S.subString(0, i) + t + S.subString(i + str.count)27             }28         }29         return S30     }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..
       
         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..

转载于:https://www.cnblogs.com/strengthen/p/10576043.html

你可能感兴趣的文章