初级算法-字符串-验证回文串

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

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

摘一个示例做个说明.
示例 1：
输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串

条件分析:

1. 只考虑字母和数字 -> 其它干扰字符串不考虑
2. 字符串 -> 字符串操作

解决思路1:

1. 根据分析1,说明我们要字符串筛选

先筛选好字符串,然后用数组接收,再采用循环一半长度来比较数据

func isPalindrome(_ s: String) -> Bool {
    let targetStr = deleteSpecialCharacters(s.lowercased())
    let sArray = Array(targetStr)
    for i in  0 ..< sArray.count / 2 {
        if sArray[i] != sArray[sArray.count - 1 - i] {
            return false
        }
    }
    
    return true
}

// 字符串筛选
func deleteSpecialCharacters(_ str: String) -> String {
    let pattern: String = "[^a-zA-Z0-9\u{4e00}-\u{9fa5}]"
    let express = try! NSRegularExpression(pattern: pattern, options: .caseInsensitive)
    return express.stringByReplacingMatches(in: str, options: [], range: NSMakeRange(0, str.count), withTemplate: "")
}

解决思路2:

采用递归操作来实现思路1

func isPalindrome(_ s: String) -> Bool {
    let targetStr = deleteSpecialCharacters(s.lowercased())
    let sArray = Array(targetStr)
    var index = 0
    while index < sArray.count / 2 {
        if sArray[index] != sArray[sArray.count - 1 - index] {
            return false
        }
        index += 1
    }
    
    return true
}

解决思路3:

采用数组反转来实现思路1

func isPalindrome(_ s: String) -> Bool {
    let targetStr = deleteSpecialCharacters(s.lowercased())

    return Array(targetStr) == Array(targetStr.reversed())
}

解决思路4:

1. 根据分析1,考虑采用数组存储有效字符,

利用数组遍历进行判断

func isPalindrome(_ s: String) -> Bool {
    var charArray:[Character] = []
    for item in s.lowercased() {
        if ( item >= "0" && item <= "9") || (item >= "a" && item <= "z")  {
            charArray.append(item)
        }
    }
    for i in 0 ..< charArray.count / 2 {
        if charArray[i] != charArray[charArray.count - 1 - i] {
            return false
        }
    }
    
    return true
}

解决思路5:

1. 根据分析1,对字符串内容进行过滤,
2. 根据分析2,对字符串进行反转

利用字符串反转进行判断

func isPalindrome(_ s: String) -> Bool {
    let str = s.filter { $0.isLetter || $0.isNumber }.lowercased()
    
    return str  == String(str.reversed())
}

解决思路6:

1. 根据分析1,对字符串进行小写转换,

采用数组存储内容和双指针方式进行判断

func isPalindrome(_ s: String) -> Bool {
    // 在初始化的就进行转换,再采用双指针相较于在对比的时候转换效率更高
    let array:[Character] = Array(s.lowercased())
    var left = 0, right = array.count - 1
    var result = true
    while left < right {
        if !array[left].isLetter && !array[left].isNumber {
            left += 1
            continue
        }
        if !array[right].isLetter && !array[right].isNumber {
            right -= 1
            continue
        }
        if array[left] != array[right] {
            result = false
            break
        }
        left += 1
        right -= 1
    }
    
    return result
}

测试用例:

回文串 let string = "A man, a plan, a canal: Panama"
无符号回文串 let string = "AmanaplanacanalPanama"
非回文串 let string = "A man, a plan, a canal: Panama12"

考察要点:

• 双指针
• 字符串