我正在尝试解决回文分割问题。您可以在https://leetcode.com/problems/palindrome- partitioning/中找到问题。
我想出了解决方案:
func partition(_ s: String) -> [[String]] { var result: [[String]] = [] func dfs(string: String, partiton: [String]) { if string.characters.count == 0 { result.append(partiton) return } for length in 1...string.characters.count { let endIndex = string.index(string.startIndex, offsetBy: length-1) let part = string[string.startIndex...endIndex] if isPalindrome(part) { let leftPart = string[string.index(after: endIndex)..<string.endIndex] print("string: \(string) part: \(part) leftpart: \(leftPart)") dfs(string: leftPart, partiton: partiton + [part]) } } } func isPalindrome(_ s: String) -> Bool { if String(s.characters.reversed()) == s { return true } else { return false } } dfs(string: s, partiton: []) return result }
但是性能很差。超过时间限制。
但是Python实现的相同想法可以通过:
def partition(self, s): res = [] self.dfs(s, [], res) return res def dfs(self, s, path, res): if not s: res.append(path) return for i in range(1, len(s)+1): if self.isPal(s[:i]): self.dfs(s[i:], path+[s[:i]], res) def isPal(self, s): return s == s[::-1]
这让我想知道如何改进swift的实现以及为什么swift的实现比python慢。
Swift String是的集合Character,并且a Character 表示单个扩展的字素簇,该簇可以是一个或多个Unicode标量。这会使某些索引操作(例如“跳过前N个字符”)变慢。
String
Character
但是第一个改进是使功能“短路” isPalindrome() 。与其完全构建反向字符串,不如将字符序列与其反向序列进行比较,并在发现差异后立即停止:
isPalindrome()
func isPalindrome(_ s: String) -> Bool { return !zip(s.characters, s.characters.reversed()).contains { $0 != $1 } }
s.characters.reversed()不会以相反的顺序创建新的集合,它只是从头到尾枚举字符。String(s.characters.reversed())但是,在方法中使用as时,将强制为反向字符串创建新的集合,这会使它变慢。
s.characters.reversed()
String(s.characters.reversed())
对于110个字符的字符串
let string = String(repeating: "Hello world", count: 10)
在我的测试中,这将计算时间从大约6秒减少到1.2秒。
接下来,避免像
let endIndex = string.index(string.startIndex, offsetBy: length-1)
然后遍历字符索引本身:
func partition(_ s: String) -> [[String]] { var result: [[String]] = [] func dfs(string: String, partiton: [String]) { if string.isEmpty { result.append(partiton) return } var idx = string.startIndex repeat { string.characters.formIndex(after: &idx) let part = string.substring(to: idx) if isPalindrome(part) { let leftPart = string.substring(from: idx) dfs(string: leftPart, partiton: partiton + [part]) } } while idx != string.endIndex } func isPalindrome(_ s: String) -> Bool { return !zip(s.characters, s.characters.reversed()).contains { $0 != $1 } } dfs(string: s, partiton: []) return result }
现在的计算时间为0.7秒。
下一步是完全避免字符串索引,并使用字符数组,因为数组索引速度很快。更好的是,使用数组 切片 来快速创建和引用原始数组元素:
func partition(_ s: String) -> [[String]] { var result: [[String]] = [] func dfs(chars: ArraySlice<Character>, partiton: [String]) { if chars.isEmpty { result.append(partiton) return } for length in 1...chars.count { let part = chars.prefix(length) if isPalindrome(part) { let leftPart = chars.dropFirst(length) dfs(chars: leftPart, partiton: partiton + [String(part)]) } } } func isPalindrome(_ c: ArraySlice<Character>) -> Bool { return !zip(c, c.reversed()).contains { $0 != $1 } } dfs(chars: ArraySlice(s.characters), partiton: []) return result }
现在的计算时间为0.08秒。
如果您的字符串仅包含“基本多语言平面”中的字符(即<= U + FFFF),则可以使用UTF-16代码点代替:
func partition(_ s: String) -> [[String]] { var result: [[String]] = [] func dfs(chars: ArraySlice<UInt16>, partiton: [String]) { if chars.isEmpty { result.append(partiton) return } for length in 1...chars.count { let part = chars.prefix(length) if isPalindrome(part) { let leftPart = chars.dropFirst(length) part.withUnsafeBufferPointer { dfs(chars: leftPart, partiton: partiton + [String(utf16CodeUnits: $0.baseAddress!, count: length)]) } } } } func isPalindrome(_ c: ArraySlice<UInt16>) -> Bool { return !zip(c, c.reversed()).contains { $0 != $1 } } dfs(chars: ArraySlice(s.utf16), partiton: []) return result }
现在,110个字符的测试字符串的计算时间为0.04秒。
因此,使用Swift字符串时可能会提高性能的一些技巧是
当然,这取决于实际用例。在 此 应用程序中,我们能够将计算时间从6秒减少到0.04秒,即150倍。