Swift 验证回文字符串 - LeetCode

作者: 韦弦Zhy | 来源:发表于2018-07-25 17:56 被阅读3次
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我哦。

相关文章

网友评论

    本文标题:Swift 验证回文字符串 - LeetCode

    本文链接:https://www.haomeiwen.com/subject/riqmmftx.html