我正在尝试解决Palindrome分区问题.你可以在
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是Characters的集合,Character表示单个扩展的Grapheme集群,可以是一个或多个
Unicode标量.这使得一些索引操作如“跳过前N个字符”变慢.
Unicode标量.这使得一些索引操作如“跳过前N个字符”变慢.
但第一个改进是“短路”isPalindrome()
功能.而不是完全构建反向字符串,比较
具有相反顺序的字符序列并尽快停止
找到差异：
func isPalindrome(_ s: String) -> Bool {
return !zip(s.characters,s.characters.reversed()).contains { $0 != $1 }
}
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字符串时可能会提高性能的一些技巧是
>按顺序迭代字符/索引.避免“跳跃”
到了第n个位置.
>如果您需要“随机”访问所有字符,请转换字符串
先到一个数组.
>使用字符串的UTF-16视图比工作更快
用角色视图.
当然这取决于实际的用例.在这个应用程序,我们能够将计算时间从6秒减少到0.04秒,这是150的因素.
