题目

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例1：

• 输入：A man, a plan, a canal: Panama
• 输出：true
• 解释：amanaplanacanalpanama 是回文串

示例2：

• 输入：race a car
• 输出：false
• 解释：raceacar 不是回文串

方法一：筛选 + 判断

思路及解法

最简单的方法先将字符串 s 通过 API，将所有字符都变为小写，得到字符串 lowercasedString，然后获取字符串 lowercasedString 中每个字符对应的 ASCII 值，并对 ASCII 值进行一次遍历，并将其中的字母和数字对应的 ASCII 值进行保留，放在数组 codeArray 中，这样我们只需要判断 codeArray 中的元素符合回文串规则即可。

判断方法一

判断的方法有两种。第一种是使用语言中的数组翻转 API 得到 codeArray 的逆序数组 reversedArray，只要这两个数组相同，那么 codeArray 就符合回文串规则，s 就是回文串。

代码

func isPalindrome(_ s: String) -> Bool {
    let lowercasedString = s.lowercased()
    var codeArray: [Int] = []
    for code in lowercasedString.utf8 {
        if (code > 96 && code < 123) || (code > 47 && code < 58) {
            codeArray.append(Int(code))
        }
    }
    let reversedArray: [Int] = codeArray.reversed()
    return reversedArray == codeArray
}

判断方法二

第二种是使用双指针。初始时，左右指针分别指向 codeArray 的两侧，随后我们不断地将这两个指针相向移动，每次移动一步，并判断这两个指针指向的 ASCII 值是否相同。当这两个指针相遇时，就说明 codeArray 符合回文串规则，s 就是回文串。

代码

func isPalindrome(_ s: String) -> Bool {
    let lowercasedString = s.lowercased()
    var codeArray: [Int] = []
    for code in lowercasedString.utf8 {
        if (code > 96 && code < 123) || (code > 47 && code < 58) {
            codeArray.append(Int(code))
        }
    }
    var left: Int = 0
    var right: Int = codeArray.count - 1
    while left < right {
        if codeArray[left] != codeArray[right] {
            return false
        }
        left += 1
        right -= 1
    }
    return true
}

复杂度分析

• 时间复杂度：，其中 是字符串 s 的长度。

• 空间复杂度：，由于我们需要将所有字母和数字字符的 ASCII 值存放在 codeArray 中，在最坏情况下，codeArray 的长度与原字符串 s 的长度相同，因此需要使用 的空间。

方法二：在原字符串上直接判断

思路及解法

我们遍历原来的字符串 s，并将每个字符加入到 stringArray 数组中，然后直接在 stringArray 上使用双指针。在移动任意一个指针时，需要不断地向另一指针的方向移动，直到遇到一个字母或数字字符，或者两指针重合为止。也就是说，我们每次将指针移到下一个字母字符或数字字符，再判断这两个指针指向的字符是否相同。

代码

func isPalindrome(_ s: String) -> Bool {
    let lowercasedString = s.lowercased()
    let stringArray = lowercasedString.map{ String($0) }
    var left: Int = 0
    var right: Int = stringArray.count - 1
    while left < right {
        let leftString = stringArray[left]
        let rightString = stringArray[right]
        if !isalnum(leftString) {
            left += 1
        } else if !isalnum(rightString) {
            right -= 1
        } else if leftString == rightString {
            left += 1
            right -= 1
        } else {
            return false
        }
    }
    return true
}

func isalnum(_ s: String) -> Bool {
    let letter = "a"..."z"
    let number = "0"..."9"
    return letter.contains(s) || number.contains(s)
}

复杂度分析

• 时间复杂度：，其中 是字符串 s 的长度。

• 空间复杂度：。