今天給大家分享一道面試中經常碰到的簡單演算法題目 - 檢測回文串，
題目：
給定一個字串，驗證它是否是回文串，只考慮字母和數字字符，可以忽略字母的大小寫，
示例1:
輸入: "A man, a plan, a canal: Panama"輸出: true
示例2:
輸入: "race a car"輸出: false
思路：
利用雙指標，
初始化兩個指標 i、j，i從字串左側開始，j從字串右側開始，我們每次將 i + 1，將 j - 1 判斷兩個字符是否相等，如果兩個指標能夠相遇就說明是回文串，不然就不是回文串，
Go代碼示例
func isPalindrome(s string) bool {// 將字串轉為小寫s = strings.ToLower(s)// 定義兩個初始化指標i, j := 0, len(s) - 1// 當 i >= j 時兩個指標相遇說明是回文for i < j {// 非字母h或數字s時左側指標加一繼續回圈if !isanum(s[i]) {i++continue}// 非字母h或數字s時右側指標減一繼續回圈if !isanum(s[j]) {j--continue}// 當對稱字符不想等說明不是回文if s[i] != s[j] {return false}i++j--}?return true}func isanum(x byte) bool {return (x >= 'A' && x <= 'Z') || (x >= 'a' && x <= 'z') || (x >= '0' && x <= '9')}
復雜度分析
-
時間復雜度：O(n)O(∣s∣)
-
空間復雜度：O(1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/233927.html
標籤：區塊鏈