Swift 验证回文字符串 - LeetCode

LeetCode.jpg

题目:验证回文字符串

描述:给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。

案例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

用Swift开始学习算法中,在LeetCode中开始做初级算法这一章节,将做的题目在此做个笔记,希望有更好方法同学们cue我哦。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端进阶之路

JS学习系列08 - 内存分配

9820
来自专栏好好学习吧

python实现栈结构

11110
来自专栏xingoo, 一个梦想做发明家的程序员

MFC常用基本数据类型

ATOM                   原子(原子表中的一个字符串的参考)  BOOL   布尔变量  BOOLEAN                布尔...

22460
来自专栏猿人谷

C++ primer里的template用法

template 的用法     在程序设计当中经常会出现使用同种数据结构的不同实例的情况。例如:在一个程序中     可以使用多个队列、树、图等结构来组织数据...

23650
来自专栏Java帮帮-微信公众号-技术文章全总结

Java企业面试——Java基础

1. Java基础部分 1.1 Java中的方法覆盖(Overwrite)和方法重载(Overloading)是什么意思? 重载Overload表示同一个类中...

29440
来自专栏blackheart的专栏

[C#1] 3-基元类型、引用类型和值类型、装箱拆箱

1.基元类型 编译器直接支持的数据类型成为基元类型。基元类型与FCL中的类型有直接的映射关系[int=Int32],这样我们可以简化的方式书写代码,并且编译后的...

22350
来自专栏跟着阿笨一起玩NET

AnonymousType匿名类型和对象之间的转换

本文转载:http://www.cnblogs.com/dean-Wei/p/3150553.html

29110
来自专栏数说戏聊

SUBSTRING() 与 CONV() 函数1.substring()函数2.conv()函数

MySQL 字符串截取函数:left(), right(), substring(), substring_index()。

9820
来自专栏GreenLeaves

JavaScript引用类型之Array数组的栈方法与队列方法

一、栈方法 ECMAScript数组也提供了一种让数组的行为类似与其他数据结构的方法。具体的来说,数组可以变现的向栈一样,栈就是一种可以限制插入和删除向的数据结...

20460
来自专栏杂烩

spring的spel 转

 Spring 3.0 创建了一种新的方式用以配置对象的注入(set注入或者构造参数注入),它便是SpEL (Spring Expression Languag...

8230

扫码关注云+社区

领取腾讯云代金券