题目:验证回文字符串
描述:给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
案例1:
输入: "A man, a plan, a canal: Panama"
输出: true
案例2:
输入: "race a car"
输出: false
方案一:将字符串中时字母和数字的元素添加到一个数组中,复制该数组然后逆转和原数组比较
代码一:
func isPalindrome(_ s: String) -> Bool {
if s.count <= 1 {
return true
}
func isCharacterOrNumber(_ character: Character) -> Bool {
if character >= "a" && character <= "z" {
return true
}
if character >= "0" && character <= "9" {
return true
}
return false
}
let lowerS = s.lowercased()
var sArr = [String]()
for character in lowerS {
if isCharacterOrNumber(character) {
sArr.append(String(character))
}
}
var tempArr = sArr
tempArr.reverse()
return tempArr == sArr
}
运行效率不是很高、、、
提交记录:
image.png方案二:添加两个指针分别指向字符串头尾,当遇到非字符或数字时往前移动,当发现两个指针指向的值不等时则返回false,直到相遇,最后返回true
代码二:
func isPalindrome1(_ s: String) -> Bool {
if s.count <= 1 {
return true
}
func isCharacterOrNumber(_ character: Character) -> Bool {
if character >= "a" && character <= "z" {
return true
}
if character >= "0" && character <= "9" {
return true
}
return false
}
let lowerS = s.lowercased()
var sArr = Array(lowerS)
var i = 0
var j = sArr.count - 1
while i < j {
if (!isCharacterOrNumber(sArr[i])) {
i += 1
} else if (!isCharacterOrNumber(sArr[j])) {
j -= 1
} else if (sArr[i] != sArr[j]) {
return false
} else {
i += 1
j -= 1
}
}
return true
}
相比方案一,运行效率略有提高
提交记录:
image.png方案三:与方案三解题思路一致,但参照前几次解题,使用Character效率不如使用unicodeScalars效率高,所以使用unicodeScalars解题
代码三:
func isPalindrome2(_ s: String) -> Bool {
if s.count <= 1 {
return true
}
func isCharacterOrNumber(_ character: UInt32) -> Bool {
if character >= 97 && character <= 122 {
return true
}
if character >= 48 && character <= 57 {
return true
}
return false
}
let lowerS = s.lowercased()
var ints = [UInt32]()
for scalars in lowerS.unicodeScalars {
ints.append(scalars.value)
}
var i = 0
var j = ints.count - 1
while i < j {
if (!isCharacterOrNumber(ints[i])) {
i += 1
} else if (!isCharacterOrNumber(ints[j])) {
j -= 1
} else if (ints[i] != ints[j]) {
return false
} else {
i += 1
j -= 1
}
}
return true
}
果然,运行效率爆表~~~~直接冲到了现有提交记录的第一名
提交记录:
效率爆表,冲上第一方案四:与方案三解题思路一致,但是在查看小伙伴们的提交记录时,又发现一个同样效率比较高的String的方法 func cString(using: UInt)
,返回的是一个CChar
数组
代码四:(直接抄的LeetCode第一个提交记录(ps:在我提交之前)):
func isPalindrome(_ s: String) -> Bool {
if s.count <= 1 {
return true
}
var chars = s.cString(using: .utf8)!
let count = chars.count
var i = 0
var j = count - 1
while i < j {
let iV = Int(chars[I])
if !((iV >= 48 && iV <= 57) || (iV >= 65 && iV <= 90) || (iV >= 97 && iV <= 122)){
i += 1
continue
}
let jV = Int(chars[j])
if !((jV >= 48 && jV <= 57) || (jV >= 65 && jV <= 90) || (jV >= 97 && jV <= 122)){
j -= 1
continue
}
if ((iV >= 65 && iV <= 90) || (iV >= 97 && iV <= 122)){
let dif = abs(iV - jV)
if dif != 0 && dif != 32 {
return false
}
}else {
if iV != jV {
return false
}
}
i += 1
j -= 1
}
return true
}
提交记录:
image.png
网友评论